C++ 代码

#include <iostream>
using namespace std;
const int N = 1e5+10;
const int M = 1e6+10;
char s[M];  //模式串
char p[N];  //模板串
int ne[N];  //next有时会与头文件冲突，所以用ne更好，next[i]表示子串s[1,2,,,,,,i-1,i]的最长相等前后缀的前缀最后一位下标，或者说是子串的最长相等前后缀的长度，因为我们是从下标1开始的，这也体现出了从1开始的好处
int main()
{
    ios::sync_with_stdio(false);    //cin,cout加速
    cin.tie(0);
    cout.tie(0);
    int n,m;
    int pos;
    cin >> n >> p+1 >> m >> s+1;    //直接用cin读入字符串p和s，由于p和s都是从1开始的，所以是p+1和s+1
    for(int i = 2,j = 0; i <= n; ++i){  //求ne数组，本质是模板串p与自身的匹配，因为ne[1] = 0，所以从2开始
        while(j && p[i] != p[j+1])      //匹配失败，j回退，即将模板串向右移动
            j = ne[j];
        if(p[i] == p[j+1])  //如果该位匹配成功，j就向前移动一位即使得j指向该位置
            ++j;
        ne[i] = j;  //更新next，每次移动i前，将已经匹配成功的长度记录到next中，由于j为模板串中的1~j的最后一位,所以j即为最大相同后缀(或前缀)长度，再把j与下标i对应
    }
    for(int i = 1,j = 0; i <= m; ++i){  //由于是s[i] == p[j+1],s和p都是从1开始，所以int i = 1,j = 0
        while(j && s[i] != p[j+1])  //不匹配则回退，即将模板串p向右移动，可以看成是s和j指针的物理位置都不变化，只有p向右移动j-ne[j]+1位
            j = ne[j];
        if(s[i] == p[j+1])  //匹配成功则j往前走一步，注意j是在p上面移动的，j从0开始走，直到走到模板串p的末尾，即匹配成功，j移动的位置即为成功匹配的位置
            ++j;
        if(j == n){ //因为j在p上移动的位置就是p与s成功匹配的位置,所以当j移动到n时，即整个模板串p都已经成功匹配了
            pos = i - n;    //i为当前p匹配成功时，s的对应元素位置，又因为模板串p长度为n，且答案要求数组s是从0开始计算匹配位置，所以起点为(i-n+1)-1=i-n
            cout << pos << " ";     //输出成功匹配后s对应元素的起点位置
            j = ne[j];  //继续移动j或者说模板串p,看之后的s中还有没有与p完全匹配的
        }
    }
    cout << endl;
    return 0;
}