KMP模板

#include <iostream>

using namespace std;

const int N = 10010,M = 100010;

int n,m;
int ne[N];      //next数组
char s[M],p[N];

int main()
{
    cin>>n>>p+1>>m>>s+1;    //下标从1开始

    //构造next数组
    for(int i=2,j=0;i<=n;i++)
    {
        while(j && p[i] != p[j+1]) j = ne[j];
        if(p[i] == p[j+1]) j++;
        ne[i] = j;
    }

    //匹配过程
    for(int i=1,j=0;i<=m;i++)
    {
        while(j && s[i] != p[j+1]) j = ne[j];
        if(s[i] == p[j+1]) j++;
        if(j == n)
        {
            printf("%d ",i-n);
            j = ne[j];
        }
    }
    return 0;
}