kmp
前缀函数
kmp中最重要的就是前缀函数nxt。
定义$nxt[i]$是模式串最长的前缀等于其子串$s[1...i]$的真后缀。
显然$nxt[1]=0$
很容易想到一种暴力模拟的方法（见下面的程序）：
for (int i = 2; i <= len(s); i++) { int j = 0; if (s[j + 1] == s[i - j]) j++; nxt[i] = j; }
很不幸这样的复杂度是$O(n^2)$的。
考虑怎么优化，如果用hash+二分的方法可以优化到$O(nlog{n})$，已经可以通过大部分的题目。
for (int i = 2; i <= len(s); i++) { int l = 0; r = i; while (l <= r) { int mid = (l + r) >> 1; if (hash[s[1...mid]] == hash[s[i - mid + 1...i]]) { nxt[i] = mid; l = mid + 1; } else { r = mid - 1; } } }
可是这是最优解吗？答案是否定的，我们还可以优化到$O(n)$。
我们发现刚才的方法都没有好好利用已经求出的$nxt$，我们想想怎么利用这些已知信息。
假设我们现在要求$nxt[i]$，记$j=nxt[i-1]$。则显然$s[1...j]=s[i-j...i-1]$，如果$s[j+1]=s[i]$的话，则$nxt[i]=j+1$。
如果不是呢？能不能如果直接令$j=j-1$，则这和暴力差不多。
上面的思路和之前犯了同样的错误——没有考虑已知信息。
如果每次令$j=nxt[j]$，则会的得到正确的答案（证明易证，画个图就好了）。
可以通过势能分析的方法证明其复杂度是正确的。
for (int i = 2, j = 0; i <= len(s); i++) { while (j && s[i] != s[j + 1]) j = nxt[j]; if (s[i] == s[j + 1]) j++; nxt[i] = j; }
kmp
kmp算法和求nxt大同小异，如果我们每次记录一个f数组$f_i$代表文本串以第i个字符结尾的后缀与模式串的前缀的最长公共长度。
求法与求nxt基本一样，只用加一句如果当前长度为模式串大小也跳nxt。
//s是模式串，t是文本串 for (int i = 1, j = 0; i <= len(t); i++) { while (j && (j == len(s) || t[i] != s[j + 1])) j = nxt[j]; if (t[i] == s[j + 1]) j++; f[i] = j; }
当然，前缀函数不止做字符串匹配这一种作用。
求最小周期
周期，即可以重复多次而得到原串的串。
如abaaba的最小周期就是aba。
aabbaabbba
具体怎么求呢？
如果$n-nxt[n]|n$，则为$n-nxt[n]$，否则为n。
首先可以证明这样做是正确的。
如果两个nxt有相交，且满足上述要求，易证这是对的。
如果没有相交，则不可能满足上述要求。
再证这是最小的，可以用反证法，如果还有更小的，则可以推出还有更大的nxt[n]，矛盾。
kmp自动机
首先什么是DFA（确定有限状态自动机），其实就是对于每个状态，和字符集，都可以转移到另一个状态。
状态在kmp这就是匹配长度。
我们现在需要求出一个数组$ch[i][j]$表示状态i后加一个字符j会得到哪个状态。
有初值$ch[0][s[1]]=1$。
那怎们在线性时间内求出呢（$O(sum n)$）。
有一个直观的想法就是枚举每一位和下一位的字符，然后暴力跳nxt。
这样固然可做，但还是犯了没有利用已知信息的错误。
如果$j=s[i+1]$，那直接指向i+1。
如果不，可以指向$ch[nxt[i]][j]$，这一步很好理解，因为$nxt[i]<i$，所以$ch[nxt[i]][j]$一定是之前已经求出来的，这样就可以在接近线性的时间复杂度内构建自动机了。
扩展kmp
z函数
我的字符串下标都是从1开始的
现在要你求一个数组z，$z_i$代表字符串s的后缀$s[i...|s|]$的最长和s相同的前缀。
求法类似manacher。
首先$z_1=|s|$不需要我们求。
从$i=2$开始，同时维护两个指针$r,l$，分别指向历史最远匹配位置，和那次匹配的初始位置（是不是类似马拉车）。
如果$i leq r$，根据已知信息可以得到$z[i] geq z[i-l+1]$，可以先令$z[i]=z[i-l+1]$，然后再暴力匹配。
和马拉车一样，不能超过已知范围，所以还要和$r-i+1$取个min。
之后就可以暴力匹配了。
因为r是在不断往后移动的，所以复杂度是$O(|s|)$的（是不是和马拉车一模一样）。
void Z(char *s, int *z) { int len = strlen(s + 1); for (int i = 2, l = 1, r = 1; i <= len; i++) { if (i <= r) z[i] = min(r - i + 1, z[i - l + 1]); while (i + z[i] <= len && s[i + z[i]] == s[z[i] + 1]) z[i]++; if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } } }
匹配
现在给你两个字符串s，t。让你求s的每一个后缀与t的最长公共前缀的长度。
对于后缀i，我们把答案存到$p_i$中。
这其实就是exkmp。
就好像kmp和求nxt很像，exkmp和z函数也很像。
只用把所有和文本串有关的z改成p（即取min中的z不动）。
然后暴力匹配时把i+z[i]改成文本串即可。
void exkmp(char *s, char *t, int *p, int *z) { int len = strlen(s + 1); for (int i = 1, l = 0, r = 0; i <= len; i++) { if (i <= r) p[i] = min(r - i + 1, z[i - l + 1]); while (i + p[i] <= len && s[i + p[i]] == t[p[i] + 1]) p[i]++; if (i + p[i] - 1 > r) { l = i; r = i + p[i] - 1; } } }
现在你可以ACluogu的模板题了（https://www.luogu.com.cn/problem/P5410）。
exkmp还有一种不优秀（我觉得）的写法，我会在附录A中给出。
如果第一个字符串的前缀$s1[1...i]$是环的话则必然有一个$1 leq j < i$，满足$s1[1...j]=s2[j+1...i],s1[j+1...i]=s2[1...j]$。
所以要做两遍exkmp，定义p1为s1位文本串，s2为模式串的p，p2反过来定义。
所以我们现在找到一个位置i，则$s2[1...p1[i]]=s1[i...i+p1[i]-1]$，现在只要$p2[p1[i]+1] geq i-1$，即可以够到i即可满足条件。
将答案与$i+p1[i]-1$取max，最后输出答案。
即$ans = max_{p2[p1[i]+1] geq i-1} i+p1[i]-1$
#include <bits/stdc++.h> using namespace std; const int N = 2000010; int n; char s1[N], s2[N]; int z1[N], z2[N]; int p1[N], p2[N]; int ans; void Z(char *s, int *z) { int len = strlen(s + 1); for (int i = 2, l = 1, r = 1; i <= len; i++) { if (i <= r) z[i] = min(r - i + 1, z[i - l + 1]); while (i + z[i] <= len && s[i + z[i]] == s[z[i] + 1]) z[i]++; if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } } } void exkmp(char *s, char *t, int *p, int *z) { int len = strlen(s + 1); for (int i = 1, l = 0, r = 0; i <= len; i++) { if (i <= r) p[i] = min(r - i + 1, z[i - l + 1]); while (i + p[i] <= len && s[i + p[i]] == t[p[i] + 1]) p[i]++; if (i + p[i] - 1 > r) { l = i; r = i + p[i] - 1; } } } void cmax(int &x, int y) { if (y > x) x = y; } int main() { scanf("%d", &n); scanf("%s", s1 + 1); scanf("%s", s2 + 1); Z(s1, z1); Z(s2, z2); exkmp(s1, s2, p1, z2); exkmp(s2, s1, p2, z1); for (int i = 1; i <= n; i++) if (p2[p1[i] + 1] >= i - 1) cmax(ans, i + p1[i] - 1); printf("%d", ans); return 0; }
完结撒花✿✿ヽ(°▽°)ノ✿。
附录A exkmp的不优秀写法
void get_nxt(char t[], int p) { nxt[p][1] = n; nxt[p][2] = 0; while (t[nxt[p][2] + 2] == t[nxt[p][2] + 1]) nxt[p][2]++; for (int i = 3, p0 = 2, r = p0 + nxt[p][p0] - 1; i <= n; i++) { if (i + nxt[p][i - p0 + 1] - 1 < r) nxt[p][i] = nxt[p][i - p0 + 1]; else { nxt[p][i] = max(r - i + 1, 0); while (t[i + nxt[p][i]] == t[1 + nxt[p][i]]) nxt[p][i]++; p0 = i; r = p0 + nxt[p][p0] - 1; } } } void exkmp(char s[], char t[], int p) { extend[p][1] = 0; while (s[extend[p][1] + 1] == t[extend[p][1] + 1]) extend[p][1]++; for (int i = 2, p0 = 1, r = p0 + extend[p][p0] - 1; i <= n; i++) { if (i + nxt[p][i - p0 + 1] - 1 < r) extend[p][i] = nxt[p][i - p0 + 1]; else { extend[p][i] = max(r - i + 1, 0); while (s[i + extend[p][i]] == t[1 + extend[p][i]]) extend[p][i]++; p0 = i; r = p0 + extend[p][p0] - 1; } } }
这里nxt是z，extend是p。
如果遇到其他有关kmp和exkmp的套路或有趣的思维我会补上