明天就是除夕了, 今天下午看KMP心态大崩, 版本太多了, 花了6h终于通透各个版本的区别.

版本一: next数组 PM表 LPS 串从位置1而不是0存储

yxc叫next 王道叫PM表(部分匹配值的表) 算法导论叫LPS(最长回文序列)数组

版本二: next数组 串从0存储

版本一的基础上, 数组整体右移一位, 左边补上一位-1, 右边去掉最后一位.
Mooc浙大数据结构 王道

版本三: next数组 串从1存储

版本二的基础上, 数组整体加一, 开头先写0,1, 考研大多考这个. 408考点 王道(重点) 严蔚敏的数据结构 KMP三人发的论文

版本四: nextval数组

不常见 next数组的基础上进一步优化
王道

yxc 推荐的模板 (版本一):

例如串abcac:
版本一王道书上与yxc模板计算出来的都是00010.

例如串ababaaababaa:
版本三王道书上是s[i]与p[j]比较, 而yxc是s[i]与p[j + 1]比较. 写出的代码就会有很大的区别.
版本一:串ababaaababaa的next数组为001231123456.
版本三:串ababaaababaa的next数组为011234223456.
001231123456整体右移一位,左边补一位-1,右边去掉一位, 再整体加1,就得到011234223456.

我会计算版本一的, 易于理解, 易于人类计算, yxc也用的这个.
考研爱考版本三, 开头先写0,1.
我考研时好像是先计算版本一的数组,再通过换算成版本三的next数组.
而且考研数据结构真题答案大多是依据版本三, 也见过版本一和版本二.

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

char p[N], s[N];
int ne[N];

int n, m;

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

    for(int i = 2, j = 0; i <= n; i ++)  // i从2开始!!!!!
    {
        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 + 1 - 1 << " ";
            j = ne[j];  // 难点
        }

    }

    return 0;
}