之前借鉴了某个模板的代码。我个人认为这份代码写得很好。值得一背。

#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int Next[N];

int main(){

    string A,B;

    cin>>A>>B;

    int lena=A.size(),lenb=B.size();

    int t1=0,t2=-1;

    Next[0]=-1;

    while(t1<lenb){

        if(t2==-1||B[t1]==B[t2]){

            t2++;

            Next[++t1]=t2;

        }

        else t2=Next[t2];

    }

    int i,j,ans=-1;

    i=j=0;

    while(i<lena){

        if(j==-1||A[i]==B[j])i++,j++;

        else j=Next[j];

        if(j==lenb){

            printf("%d\n",i-lenb+1);

            j=Next[j];

        }

    }

    for(int i=1;i<=lenb;i++){

        if(i>1)putchar(' ');

        printf("%d",Next[i]);

    }

    return 0;

}