原题链接

Description

模板题啦~

Code

//【模板】KMP字符串匹配

#include <cstdio>

#include <cstring>

int const L=1e6+10;

char s1[L],s2[L];

int nxt[L];

int main()

{

    scanf("%s",s1+1); scanf("%s",s2+1);

    int L1=strlen(s1+1),L2=strlen(s2+1);

    nxt[0]=-1;

    for(int i=1;i<=L2;i++)

    {

        int x=nxt[i-1];

        while(x!=-1&&s2[x+1]!=s2[i]) x=nxt[x];

        nxt[i]=x+1;

    }

    for(int i=0,j=0;i<=L1;i++)

    {

        if(j==L2) printf("%d\n",i-L2+1);

        while(j&&s1[i+1]!=s2[j+1]) j=nxt[j];

        if(s1[i+1]==s2[j+1]) j++;

    }

    for(int i=1;i<=L2;i++) printf("%d ",nxt[i]);

    return 0;

}