KMP
陈子骏
2018-04-02 17:46:41
```
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
int next[1100001];
char a[1100001],b[1100001];
int lena,lenb;
void getfail()
{
for(int i=1;i<lenb;i++)
{
int j=next[i];
while(j&&b[i]!=b[j])j=next[j];
next[i+1]=b[i]==b[j]?j+1:0;
}
}
void kmp()
{
int j=0;
for(int i=0;i<lena;i++)
{
while(j&&a[i]!=b[j])j=next[j];
if(a[i]==b[j])j++;
if(j==lenb)printf("%d\n",i-lenb+2);
}
}
int main()
{
scanf("%s%s",a,b);
lena=strlen(a);
lenb=strlen(b);
getfail();
kmp();
for(int i=1;i<=lenb;i++)
printf("%d ",next[i]);
return 0;
}
```