KMP算法模板

#include <cstdio>

using namespace std;

const int N = 100010, M = 1000010;
char p[N], s[M];
int ne[N];

int main(void)
{
    int n, m;
    scanf("%d %s %d %s", &n, p + 1, &m, s + 1);

    // 构造next数组;存放以 i 结束的字符串的最长公共前缀的长度 j
    // 构造过程其实就是模式串初始错开一位，每轮以 i 为字符串匹配结尾，找匹配字符串的过程
    // 而 j 刚好可以反映前缀长度
    ne[1] = 0;
    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;
    }

    // 匹配过程 
    // 模式串总是错一位去和主串比主要是为了在不匹配时，迎合next数组的概念
    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;
}