KMP算法，是一种能在 \(O(n+m)\) 的时间内求出模式串 \(A\)（长度为 \(m\)）在文本串 \(B\)（长度为 \(n\)） 中出现的次数及位置的字符串匹配算法。
KMP算法共分为 \(2\) 步：
第 \(1\) 步，对 \(A\) 串进行自我匹配，求出 \(nxt\) 数组，\(nxt[i]=max\{j\}\)，其中 \(j<i\) 且 \(A[i-j+1 \sim j]=A[1 \sim j]\)。
第 \(2\) 步，用 \(A\) 串去匹配 \(B\) 串，求出 \(f\) 数组，其中 \(f[i]=max\{j\}\)，其中 \(j \leq i\) 并且 \(B[i-j+1 \sim i]=A[1 \sim j]\)。
如何快速计算 \(nxt\) 数组？
若 \(j_0\) 是 \(nxt[i]\) 满足条件的选项（以下称为“候选项”），那小于 \(j_0\) 中最大的候选项是 \(nxt[j_0]\)。
在计算 \(nxt[i]\) 时，只要把 \(nxt[i-1]+1\)，\(nxt[nxt[i-1]]+1\)，\(...\) 作为候选项即可。
\(f\) 数组可以用相同方法计算。
#include<iostream>
#include<cstring>
#define MAXN 1000005
using namespace std;
int Next[MAXN];
int len_a,len_b;
char a[MAXN],b[MAXN];
int main(){
cin >> a+1;
cin >> b+1;
len_a = strlen(a+1);
len_b = strlen(b+1);
Next[1] = 0;
for (int i = 2,j = 0; i <= len_b; i++){
while(j > 0 && b[i] != b[j+1]) j = Next[j];
if(b[i] == b[j+1]) j++;
Next[i] = j;
}
for (int i = 1, j = 0; i <= len_a; i++){
while(j > 0 && b[j+1] != a[i]) j = Next[j];
if (b[j+1] == a[i]) j++;
//输出匹配位置，然后继续匹配
if (j == len_b) { cout << i-len_b + 1 << endl; j = Next[j];}
}
for (int i = 1; i <= len_b; i++)
cout << Next[i] << " ";
return 0;
}