kmp算法：扫描字符串A，并且更新可以匹配到B的什么位置。时间复杂度O(n)。
P[i]表示当前模式串在该位置匹配冲突时，应该将模式串的哪一位与此对齐。
总之就是扫描字符串A，并更新2可以匹配到什么位置
点击查看代码
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
#define N 1000005
using namespace std;
int p[N];//当前匹配到j个字母和j+1个字母不能匹配的时候，新的j的最大值是多少：p[1]=0
signed main()
{
ios;
string A,B;cin>>A>>B;
A=" "+A;B=" "+B;
int la=A.size()-1,lb=B.size()-1,j,i;
for(i=2,j=0;i<=lb;i++)
{
while(j&&B[i]!=B[j+1])j=p[j];//不能匹配且j还没到0后退一步
if(B[i]==B[j+1])j++;
p[i]=j;
}
for(i=1,j=0;i<=la;i++)
{
while(j&&A[i]!=B[j+1])j=p[j];//不嫩继续匹配且j还没减少到0，减少j的值
if(A[i]==B[j+1])j++;//能继续匹配j+1
if(j==lb)
{
cout<<i-lb+1<<endl;//输出字串首在字符串中的位置
j=p[j];//继续寻找匹配（可以重叠）
}
}
for(int i=1;i<=lb;i++)cout<<p[i]<<" ";
return 0;
}