洛谷3375
1 #include<cstdio> 2 #include<cstring> 3 const int maxn=1000100; 4 int lp,lt,j,f[maxn]; 5 char p[maxn],t[maxn]; 6 7 void getfail() { 8 f[1]=1; f[2]=1; j=1; 9 for (int i=2;i<=lt;i++) { 10 j=f[i]; 11 while(j>1&&t[i]!=t[j]) j=f[j]; 12 if (t[i]==t[j]) f[i+1]=j+1; 13 else f[i+1]=1; 14 } 15 } 16 17 int main() { 18 scanf("%s",p+1); 19 scanf("%s",t+1); 20 lp=strlen(p+1); lt=strlen(t+1); 21 getfail(); 22 j=1; 23 for (int i=1;i<=lp;i++) { 24 while(j>1&&p[i]!=t[j]) j=f[j]; 25 if (p[i]==t[j]) { 26 if (j==lt) printf("%d ",i-lt+1); 27 j++; 28 } 29 } 30 for (int i=1;i<=lt;i++) printf("%d ",f[i+1]-1); 31 return 0; 32 }