(kmp) $O(n)$

C++ 代码

#include <iostream>

using namespace std;

const int M = 1e5 + 10, N = 1e6 + 10;

int m, n;
char p[M], s[N];
int ne[M];
//

int main() {
    cin >> m >> p + 1 >> n >> s + 1;

    //求ne数组,ne数组不仅仅跟当前值有关，还跟前面的元素有关，前面元素没有重复的就算
    //这个值有一堆也没有卵用，因为是从前往后覆盖，一个生元素全部清o了
    // 为什么要ne[j]，因为既然你能跟我相遇说明你前一个跟我前一个务必一样
    for(int i = 2, j = 0; i <= m; i++) {
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
    }

    //kmp匹配
    for(int i = 1, j = 0; i <= n; i++) {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j++;
        if(j == m) {
            j = ne[j]; //当匹配成功时继续往下匹配
            printf("%d ", i - m);
        }
    }

    return 0;
}