【模板】KMP

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 998244353;
int n, m, ne[N];
char a[N], b[N]/*母*/;

int main() {
    scanf("%d%s%d%s", &n, a + 1, &m, b + 1);
    for (int i = 2, j = 0; i <= n; ++i) {
        while (j && a[i] != a[j + 1]) j = ne[j];
        if (a[i] == a[j + 1]) j++;
        ne[i] = j;
    }
    for (int i = 1, j = 0; i <= m; ++i) {
        while (j && b[i] != a[j + 1])j = ne[j];
        if (b[i] == a[j + 1]) j++;
        if (j == n) {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}