KMP算法，求模式串的NEXT[J]=K函数，是我理解错误，还是书本错误？

Question

KMP查找模式串P在主串S中的位置。

计算模式串P的Next[j]=k函数。

意义：
设有主串S，模式串P，主串S和模式串P的前j个字符已经完全匹配(0~j-1,共j个)。
如果在P[j]上失配，即P[j]!=S[j]。
那么下一次比较，只需用P[k]与S[j]进行比较。(0<=k<j,且k使得P[0]~P[k]完全相同于P[j-1-k]~P[j-1])。

书上给出的算法是：

void bookNext(char* P, int * pNext) {
    int i, j, slen;
    slen = strlen(P); i = 0;
    pNext[0] = -1; j = -1;
    while (i < slen) {
        if (j == -1 || P[i] == P[j]) { ++i; ++j; pNext[i] = j; }
        else j = pNext[j];
    }
}

我自己写了个完整的程序，nextJ也是自己实现的。

#include "stdafx.h"
#include <iostream>
#include "stdlib.h" //rand(), srand()

#include <string>

using namespace std;

void NextJ(char* P, int* pNext) {
    pNext[0] = -1;
    pNext[1] = 0;
    int j, k, i;
    string tmpStr;
    tmpStr = P;
    int maxK;
    cout << tmpStr << endl;
    for (j = 2; j < (int)strlen(P); j++) {
        maxK = 0;
        for (k = 0; k <= (j - 1); k++) {
            if (k >= (j - 1 - k)) break; // 使得左区间的右边界 < 右区间的左边界
            pNext[j] = 0;
            for (i = 0; i <= k; i++) {
                if (P[i] != P[(j - 1) - k + i]) break;
            }
            // 在当前的k下，首尾相同，
            if (i == k + 1) {
                maxK = k + 1;
            }
        }
        pNext[j] = maxK;
        cout << "--------------------------------" << endl;
        cout << "j=" << j << ", J_str=" << tmpStr.substr(0, j) << endl;
        cout << "k=" << to_string(maxK) << ", left_str=" << tmpStr.substr(0, maxK + 1) << ", right_str=" << tmpStr.substr((j - 1) - maxK, maxK + 1) << endl;
        cout << "next[" << j << "]=" << pNext[j] << endl;
        cout << endl;
    }
}

void bookNext(char* P, int * pNext) {
    int i, j, slen;
    slen = strlen(P); i = 0;
    pNext[0] = -1; j = -1;
    while (i < slen) {
        if (j == -1 || P[i] == P[j]) { ++i; ++j; pNext[i] = j; }
        else j = pNext[j];
    }
}

void main()
{
    system("chcp 65001");

    string strP, strS;
    strS = "abacbcabababbcbc";
    strP = "abababb";

    char *charP, *charS;
    // 将string类型转换成char *类型
    const char * constc;
    constc = strP.c_str();
    charP = const_cast<char*>(constc);

    constc = strS.c_str();
    charS = const_cast<char*>(constc);
    int *nextP = new int[strlen(charP)];
    int *bNext = new int[strlen(charP)];
    //next(charP, nextP);
    NextJ(charP, nextP);
    cout << "=================bookNext output==============" << endl;
    bookNext(charP, bNext);
    for (int i = 0; i < (int)strlen(charP); i++) {
        cout << "bNext[" << to_string(i) << "] = " << bNext[i] << endl;
    }
}

主串和模式串在完整程序中。
书上对输出结果画了个图：

我运行了一遍程序，我的输出和结果图一样的(我从J=2开始计算)：
但书上的next函数的输出是这样的：

Active code page: 65001
abababb
--------------------------------
j=2, J_str=ab
k=0, left_str=a, right_str=b
next[2]=0

--------------------------------
j=3, J_str=aba
k=1, left_str=ab, right_str=ba
next[3]=1

--------------------------------
j=4, J_str=abab
k=2, left_str=aba, right_str=bab
next[4]=2

--------------------------------
j=5, J_str=ababa
k=1, left_str=ab, right_str=ba
next[5]=1

--------------------------------
j=6, J_str=ababab
k=2, left_str=aba, right_str=bab
next[6]=2

=================bookNext output==============
bNext[0] = -1
bNext[1] = 0
bNext[2] = 0
bNext[3] = 1
bNext[4] = 2
bNext[5] = 3
bNext[6] = 4

D:\AtomFiles\DataStructCode\KMPstring\Debug\KMPstring.exe (进程 8648)已退出，返回代码为: 0。
按任意键关闭此窗口...

从逻辑上来看，似乎bookNext也不对。

是我没理解KMP算法，还是书上有错啊？

Answer 1

bNext数组的结果是正确的。（书中的图应该是错了，哪本书在多少页你也说下，方便我们查查）

你自己写的NextJ我没细看，但是看结果，是不对。

对next数组的理解具体可以参考：https://subetter.com/articles...