和y总的1-indexed的模版类似
这里每次是用s[i]和p[j]匹配

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    int n, m;
    string s, p;
    cin >> n >> p >> m >> s;

    vector<int> nxt(n); // nxt[j]表示p[0:j]的最长前后匹配缀的长度
    for(int i = 1; i < n; ++i)
    {
        // j可以初始化为nxt[i-1]的值，由于nxt[i-1]是长度且j的坐标从0开始，
        // 所以j直接指向p中i-1的最长前缀后一位, 可以直接用来和p[i]尝试匹配
        int j = nxt[i-1];
        // p[i]和p[j]不匹配的话，j指向nxt[j-1]，同理，也可以用来和p[i]进行尝试匹配
        while(j && p[i] != p[j]) j = nxt[j-1];
        if(p[i] == p[j]) j++;
        nxt[i] = j;
    }

    for(int i = 0, j = 0; i < m; ++i)
    {
        while(j && s[i] != p[j]) j = nxt[j-1];
        if(s[i] == p[j]) j++;
        if(j == n)
        {
            cout << i-n+1 << ' ';
            j = nxt[j-1];
        }
    }
    cout << endl;

    return 0;
}