C++代码

记个板子

#include <iostream>
#include <cstdio>
#include <cstring>
#include  <string>

using namespace std;

const int N = 1e6 + 5;
int n, m;
char p[N], s[N];
int ne[N];
int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    //求next
    for(int i = 2, j = 0; i <= n; i ++)
    {
        while(p[i] != p[j + 1] && j) j = ne[j];
        if(p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }
    //匹配
    for(int i = 1, j = 0; i <= m; i ++)
    {
        while(s[i] != p[j + 1] && j) j = ne[j];//必须判断j是否不等于0
        if(s[i] == p[j + 1]) j ++;
        if(j == n)
        {
            cout << i - n << " ";
            j = ne[j];
        }
    }
    return 0;
}