KMP算法的一些自己理解

本蒟蒻刚开始学算法，所以可能有很多地方会理解错误，欢迎大佬指点。
首先有两个字符串p[N]和s[M]
p[N]为模式串，s[M]为模板串
我们需要在模板串s[M]上找到一个子串和模式串p[N]完全相同
当发现s[i]与p[j + 1]不同时我们调用ne[j]（我们调用的是ne[j]不是ne[j + 1]）,这是为什么呢？

如上图，当i = 4， j = 3的时候s[i] != p[j + 1],但是前面j的元素都以匹配，我们令j = ne[j] = 1。但是s[i]还是不等于p[j + 1]，再次让j = ne[j] = 0;那么j + 1 = 1, i = 4。跳出循环j指向的位置还是0，i = 5在与j = 0开始匹配

那我们现在来解释一下ne[j]是什么含义，如图当j = 3时aba已经匹配成功，要找一个最大的前缀让前面匹配的继续保持匹配状态，也就是找一个最大的前缀和后缀相同。
比如ababc前面四个均已匹配第五个不匹配此时j = 4不匹配，那么只需要将第一个ab移动到第二个ab上继续匹配即可，在对后面没有匹配的元素继续匹配。

题目描述

给定一个字符串 S，以及一个模式串P，所有字符串中只包含大小写英文字母以阿拉伯数字。
模式串 P在字符串 S中多次作为子串出现。
求出模式串 P在字符串 S中所有出现的位置的起始下标。

样例

3
aba
5
ababa

C++ 代码

#include <iostream>

using namespace std;

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

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

    for(int i = 2, j = 0; i <= n; i ++)
    {
        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 ++)
    {
        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;
}