KMP 详解
KMP数组存的是什么
对于一个字符串 b,下标从1开始。
则kmp[i]表示 以i结尾的连续子串 = s的前缀的最大值（等价于前缀最大结尾处）
如何求KMP
假设 i 以前的KMP都被求出来了。
j 表示上一个字符可以成功匹配的长度（等价于下标）
如果b[j+1] != b[i]下一个位置匹配不上（即不能成为前缀）
则，让j = kmp[j] 即成为以j结尾的 连续子串 的 最长前缀 尾部的下标
退出循环后，若还能匹配上则j++(本质是，加上i的贡献。因为j = 0时可能匹配不上)
然后让kmp[i] = j即可。
运用kmp
和求kmp差不多，如果匹配不上，求让a[i]和以j结尾的连续子串的最长前缀匹配。（放宽要求）
算法正确性证明
用哲学的话来说就是，每一次失败都会让我变得更强大。
当匹配不上时，匹配串b至少会前移1位，由指针的思想。O(n)可证。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
int kmp[N];
string a,b;
int j;
int main(){
cin>>a>>b;
a = " "+a;
b = " "+b;
for(int i = 2;i < b.size();i++){
while(j&&b[j+1] != b[i]){
j = kmp[j];
}
if(b[j+1] == b[i])j++;
kmp[i] = j;
}
j = 0;
for(int i = 1;i < a.size();i++){
while(j&&a[i] != b[j+1]){
j = kmp[j];
}
if(b[j+1] == a[i])j++;
if(j == b.size()-1){
cout<<i-(b.size()-1)+1<<endl;
j=kmp[j];
}
}
for (int i=1;i < b.size();i++)cout<<kmp[i]<<" ";
return 0;
} 