在线IDE和c++上运行结果都没问题,交到luogu上全re
码(可能有点丑
#include<bits/stdc++.h>
using namespace std;
char a[1000011],s[1000011];
int next[1000011],n,m;
void gnext(){
int q=0;
for(int i=2;i<=n;i++){
while(s[q+1]!=s[i]&&q>0){q=next[q];}
if(s[q+1]==s[i])q++;
next[i]=q;
}
}
int kmp() {
int j=0;
for(int i=1;i<=m;i++){
while(j>0&&s[j+1]!=a[i])j=next[j];
if(s[j+1]==a[i])j++;
if(j==n){
cout<<i+1-n<<endl;
j=next[j];
}
}
}
int main() {
scanf("%s%s",a+1,s+1);
m=strlen(a+1);
n=strlen(s+1);
gnext();
kmp();
for(int i=1; i<=n; i++)cout<<next[i]<<" ";
return 0;
}
1.in
CEBDAEEAACEBDAE
EBDAE
1.out
2
11
0 0 0 0 1