KMP 是可以在文本串$s$中快速查找模式串$p$的一种算法。

部分匹配表

$pmt[i]$ 就是，从 $p[0]$ 往后数、同时从 $p[i]$ 往前数相同的位数，在保证前后缀相同的情况下，最多能数多少位。（但要 小于 $p$的长度）

线性规划题，真前缀后缀的前缀和都往后添加。

故而可以用前缀去匹配后缀。

此过程还可以顺带求出前面的部分匹配表，即失配后往前移动模式串到未失配且最优时，

正确且复杂度为 $O(2n)$

匹配

若失配，则直到模式串成功匹配或移到头时继续。

因为每当 $j$ 往后移了，则之后 $i$ 必定往后移动（部分决定 $j$ 到底可以往前移几位），

算法正确，且时间复杂度为 $O(2n)$

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n, m;
int pmt[N];
char p[N], s[N];

int main()
{
    scanf("%d%s%d%s", &n, p, &m, s);
    for (int i = 1, j = 0; i < n; pmt[i ++ ] = j)
    {
        while (j && p[i] != p[j]) j = pmt[j-1]; // 不匹配
        if (p[i] == p[j]) j ++; // 匹配就往前走
    }

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