KMP算法（第一次自己口述复盘）
正在缓冲...
#include<bits/stdc++.h>
using namespace std;
const int M=1e8;
char a[M],b[M]; //a为长串，b为子串
int asize,bsize,ne[M],ans=0;
int main()
{
cin>>a+1>>b+1;
asize=strlen(a+1);
bsize=strlen(b+1);
for(int i=2,j=0;i<=bsize;i++) //求最长前缀后缀相等位置数组
{
while(j&&b[i]!=b[j+1]) j=ne[j];
if(b[i]==b[j+1]) j++;
ne[i]=j;
}
for(int i=1,j=0;i<=asize;i++) //匹配子串与长串
{
while(j&&a[i]!=b[j+1]) j=ne[j];
if(a[i]==b[j+1]) j++;
if(j==bsize)
{cout<<i-j+1<<" ";
j=ne[j];
ans++;}
}
cout<<"\n";
cout<<ans;
return 0;
}
题目可以在洛谷或者acwing上面找到，该代码为本人复盘模板
顶部