KMP

字符串匹配，正常匹配模式串P不匹配时每次都要从头开始，复杂度太高
KMP就是多了一个ne[N]数组，记录的是当模板串第j + 1个字母与模式串第i个字符不匹配时，跳转到ne[j]
ne[j]表示的是以j字符为终点长度仅次于 [1, j]的长度 [1, ne[j]]

怎么求ne[j], 用模板串和模板串做字符串匹配ne[i] = j(匹配的长度)

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
char p[N], s[N];
int ne[N];//ne[j]表示 第j + 1不匹配 第二长的是[1, ne[j]], 并判断ne[j] + 1与i是否匹配

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

    //i 和 j + 1表示待匹配的字符下标, i从2开始 因为ne[1] = 0
    for(int i = 2, j = 0; i <= n; ++ i) {//求ne[j]数组
        while(j && p[j + 1] != p[i]) j = ne[j];//j + 1与i不匹配 跳转到ne[j]直到模版串j = 0
        if(p[j + 1] == p[i]) ++ j;//匹配成功，匹配下一个
        ne[i] = j;
    }

    //i 和 j + 1表示待匹配的字符下标
    for(int i = 1, j = 0; i <= m; ++ i) {
        while(j && p[j + 1] != s[i]) j = ne[j];
        if(p[j + 1] == s[i]) ++ j;
        if(j == n) {//匹配成功
            cout << i - n << " ";// 起始下标 = (i - n + 1) - 1 最后减去1是因为我们是下标从1开始
            j = ne[j];//更新j下标
        }
    }
    return 0;
}