洛谷3375

1 #include
      
        2 #include
       
         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\n",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 }