@[tiandragon00](/space/show?uid=33639)
希望更丰富的展现？[使用Markdown](https://www.luogu.org/wiki/show?name=%E5%B8%AE%E5%8A%A9%EF%BC%9Amarkdown)
by Smile_Cindy @ 2019-03-19 18:49:03
@[tiandragon00](/space/show?uid=33639)
希望更丰富的展现？[使用Markdown](https://www.luogu.org/wiki/show?name=%E5%B8%AE%E5%8A%A9%EF%BC%9Amarkdown)
by Smile_Cindy @ 2019-03-19 18:49:08
## 希望更丰富的展现？使用Markdown
by Froggy @ 2019-03-19 18:49:42
```cpp
#include<bits/stdc++.h>
using namespace std;
int next[1000005];
char t[1000005],p[1000005];
int x,y;
void KMP(char t[1000005], char p[1000005])
{
int flag=0;
int i = 0;
int j = 0;
int x=strlen(t); //cout<<"asdf"<<x<<endl;
int y=strlen(p);
//cout<<x<<" "<<y<<endl;
while (i < x && j <y)
{
if (j == -1 || t[i] == p[j])
{
//printf("i=%d,j=%d\n",i,j);
i++;
j++;
}
else
j = next[j];
if(j==y)
{
printf("%d\n",i-j+1);
flag=1;
j=next[j];
}
}
if(flag==0)
cout<<-1<<endl;
}
void getNext(char p[1000005], int next[1000005])
{
next[0] = -1;
int i = 0, j = -1;
while (i <= strlen(p))
{
if (j == -1 || p[i] == p[j])
{
++i;
++j;
next[i] = j;
}
else
j = next[j];
}
}
int main()
{
scanf("%s%s",t,p);
//cout<<t<<endl<<p<<endl;
getNext(p,next);
KMP(t, p);
//cout<<x+1<<endl;
x=strlen(t); //cout<<"asdf"<<x<<endl;
y=strlen(p);
for(int i=1;i<=y;i++)
printf("%d ",next[i]);
return 0;
}
```
by tiandragon00 @ 2019-03-19 18:54:24
@[Alpha](/space/show?uid=87058) 丰富展现了
by tiandragon00 @ 2019-03-19 18:55:07
我不会KMP板子~~所以用FFT过的这个题~~
by kraylas @ 2019-03-19 19:05:25