luogu P3375

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[1000010], t[1000010];
int  nxt[1000010], m, n;

int main()
{
    scanf("%s%s", s+1, t+1);                        //用getchar和getline会神奇挂掉 
    m=strlen(s+1), n=strlen(t+1);
    nxt[0]=nxt[1]=0;
    for(int i=2, j=0; i<=n; i++)                    //推导nxt数组 
    {
        while(j && t[j+1]!=t[i])    j=nxt[j];
        if(t[j+1]==t[i])    ++j;
        nxt[i]=j;   
    }
    for(int i=1, j=0; i<=m; i++)                    //匹配 
    {
        while(j && s[i]!=t[j+1])    j=nxt[j];
        if(s[i]==t[j+1])    j++;
        if(j==n)            printf("%d\n", i-n+1);  //输出匹配位置 
    }
    for(int i=1; i<=n; i++) printf("%d ", nxt[i]);
    return 0;
}