KMP-字符串匹配算法

1.ne[j] 表示的是什么
ans：ne[j]表示模版串中第j个字符的最大前缀匹配的下标

2.为什么ne[1] == 0
ans: 因为ne表示最大前缀匹配，所以对于第一个字符串来说，他不存在最大前缀匹配，我们定义为0

3.模式串和模版串的匹配过程
ans：对于s[i]，它的前一个字符s[i - 1] 已经匹配成功，即s[i - 1] == p[j], 则j表示模版串中和模式串匹配
上的最大的下标。现在需要判断s[i] 和 p[j + 1] 是否匹配，如果匹配上，则j++, 并判断是否已经匹配完成；
如果没有匹配上，则需要去找p[j]的最大前缀匹配的下标，如果找到且 j != 0，则继续判断s[i] 和 p[j + 1] 的
关系。如果实在是没有找到，也就是说p[j]没有最大前缀匹配，即j == 0，那么模版串就应该将p[1] 和 s[i] 对齐，继续匹配。

4.模版串求ne数组的过程
ans：ne[1] 前面没有最长前缀匹配，所以等于0。对于第i个字符，如果找到它前一个字符即p[i - 1]的最大前缀
匹配p[j]，且p[i] == p[j + 1]，那么ne[i] 就等于 j + 1；如果p[i] != p[j + 1] 就继续向前找，直到找到
或者没有对应的最大前缀匹配即某个ne[j] == 0,使得j = ne[j] = 0。那么需要判断p[i] 与 p[j + 1] 也就是p[1]
是否相等，如果相等，那么ne[i] 就等于 1，否则ne[i]就等于0。

最大前缀匹配
ans：对p[i]这个字符而言，如果在前1～i-1个字符串中存在一个最长的字符串，长度为k，且有
p[1, k] == p[i-k+1, i],则称p[1, k] 是p[i]的最长前缀匹配，而ne[i]就等于k.
最长前缀匹配在模式串和模版串匹配过程中，可以用来跳过无用匹配，并且不会错过任何可能的匹配机会。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 1000010;
char s[N], p[M];
int ne[N];  //ne[j] 表示j这个字符的最长前缀的下标
int n, m;

int main() {
    scanf("%d%s", &n, p + 1);
    scanf("%d%s", &m, s + 1);

    for (int i = 2, j = 0; i <= n; i++) {//i是当前这个字符的下标，j是i-1这个字符的最大前缀匹配下标
        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++) { // i是母串中当前这个字符的下标，j是i-1这个字符在子串中的
    //最大前缀匹配的下标
        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;
}