KMP算法

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010, M = 1000010;
char p[N], s[M];
int n, m;
int ne[N];

int main(){
    cin >> n >> p + 1 >> m >> s + 1;
    //i: 1 到 n, j: 0 到 n - 1

    for(int i = 2, j = 0; i <= n; i++){  //i从2开始遍历，因为i = 1，也就是next[1] = 0 已经设置好了
        while(j && p[i] != p[j + 1]) j = ne[j];//要点： 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){
            printf("%d ", i - j);
            j = ne[j];//要点，匹配后p往后移动找到下一个可能匹配的位置
        }
    }
    return 0;
}