蒟蒻不会KMP,所以直接野蛮做法
代码
#include <bits/stdc++.h>
using namespace std;
int ans=0,a[10000001];
int main()
{
char x[1000001],y[1000001],z[1000001];
gets(x);
gets(y);
int k=1,j=0,sum=0;
int n=strlen(x);
int m=strlen(y);
for(int i=1;i<=m;i++)
z[i]=y[i-1];
for(int i=2;i<=m+1;i++)
{
while(j&&z[i]!=z[j+1])
j=a[j];
if(z[j+1]==z[i])j++;
a[i]=j;
}
j=0;
for(int i=0;i<n;i++)
{
if(x[i]==y[j]&&sum!=m)
{
sum++;
j++;
if(sum==m)
{
cout<<i-m+2<<endl;
ans++;
sum=0;j=0;
i--;
}
}
else
{
sum=0,j=0;
if(x[i]==y[j])
{
sum++;
j++;
}
}
//cout<<sum<<" ";
}
for(int i=1;i<=m;i++)
cout<<a[i]<<" ";
//cout<<ans;
return 0;
}
在下来的样例
输入
CEBDAEEAACEBDAE
EBDAE
输出
2
11
0 0 0 0 1
测试图片