KMP模板

#include <cstdio>
using namespace std;

int r[1111111];
char w[1111111];
char s[1111111];

int main()
{
    scanf("%*d");scanf("%s",w+1);
    for(int k = 1;w[k];k++)
    {
        int R=r[k];
        while(R>0&&w[R+1]!=w[k+1]) R=r[R];
        if(w[R+1]!=w[k+1]) r[k+1]=0;else r[k+1]=R+1;
    }
    scanf("%*d");scanf("%s",s+1);
    int k = 0;
    for(int i = 1;s[i];i++)
    {
        if(s[i]==w[k+1]) k+=1;
        else
        {
            while(k>0&&s[i]!=w[k+1])k=r[k];
            if(s[i]!=w[k+1])k=0;else k=k+1;
        }
        if(!w[k+1]) printf("%d ",i-k);
    }
    return 0;
}