KMP算法
用于快速找子串在原串中的位置和次数。
算法思路
先处理原串，初始化 kmp 数组。从头开始匹配，如果匹配成功下标存匹配成功的下标后一个，否则再向回找。
举个例子：
子串 ABCABCD
KMP 0001230不难发现，初始化 kmp 时第二个 $A$ 的下表是 $1$,第二个 $B$ 的下标是 $2$，这么存的原因是如果前面几位都匹配成功，下一位突然匹配失败，会从下标的地方继续而不是重新开始，这也是 KMP 的算法的核心思想。
举个有代表性的例子：
原串 ABCEFDABCEFDABCD
子串 ABCEFDABCD
KMP 0000001230前几位都可以和原串匹配成功，但是在第 $10$ 位（$1$ 为第一位）失配了。
- 如果是原来的暴力算法，那么会从第二位从新一点点匹配，第二位不行，第三位不行……第七位成功了，输出。
- 但是现在可以直接从失配位置的下标继续匹配，第一次失败后会直接从 $3$ 的
kmp下标开始继续匹配，但原数组的匹配位置不变。
到匹配完成时 ，kmp 的方法使原串每位只比对了一次，效率大大提升。
为什么失配直接回到下标继续匹配？
这和 kmp 的初始化有关，在初始化的时候，我们就比对了失配位置。比对时就是用当前下标从头开始比对的。
通俗一点：能匹配到这一步，就已经有了匹配到这里的资格。
再看上边的例子。
例子：
子串 ABCABCD
KMP 0001230能匹配到第 $5$ 位（$B$），假设下一位未匹配失败了，但是还是有回到第 $3$ 位的资格，因为前面已经匹配成功。
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
#include<cctype>
#include<stack>
#include<bitset>
#include<map>
#include<utility>
using namespace std;
long long r_r(){
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1e6+10;
char a_a[o_o],b_b[o_o];//原串，子串
int l_a,l_b,k;
int kmp[o_o];
int main(){
cin>>a_a+1>>b_b+1;
l_a=strlen(a_a+1);//原串长度
l_b=strlen(b_b+1);//子串长度
k=0;//初始化
for(int i=2;i<=l_b;i++){//处理子串
while(k&&b_b[k+1]!=b_b[i])k=kmp[k];//失配，回到失配指向的下标
if(b_b[k+1]==b_b[i])k++;//匹配成功，继续匹配
kmp[i]=k;//标记失配下标
}
k=0;//初始化
for(int i=1;i<=l_a;i++){//处理原串
while(k&&b_b[k+1]!=a_a[i])k=kmp[k];//失配，回到失配指向的下标
if(b_b[k+1]==a_a[i])k++;//匹配成功，继续匹配
if(l_b==k){//匹配完成
cout<<i-l_b+1<<endl;//输出
k=kmp[k];//回到失配下标
}
}
for(int i=1;i<=l_b;i++)printf("%d ",kmp[i]);//输出 KMP 失配下标
return 0;
}
/*
ABCEFDABCEFDABCD
ABCEFDABCD
*/ 
