C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS                     \
    ios::sync_with_stdio(false);\
    cin.tie(0)

// *start on @date: 2021-05-17 10:17 
// *writer: zyf

int main() 
{
    IOS;
    int n,m,ne[100010];
    char p[100010],s[1000010];
    cin >> n >> p + 1>> m >> s + 1;
    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;
    }
    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)
        {
            cout<<i - n<<" ";
            j = ne[j];
        }
    }
    return 0;
}