关于KMP模式匹配算法next数组计算的细节疑问

首先贴出你提到的next数组计算代码：

int GetNext(char ch[], int length, int next[]) {
    next[1] = 0;
    int i = 1, j = 0;
    while (i < length) {
        if (j == 0 || ch[i] == ch[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}

一、为什么比较第j位和第p位（而非p-1位）？ #

先明确你提到的定义：当next[j] = p时，第j位之前的子串（即S₁~Sⱼ₋₁）的最长公共前后缀长度是p-1。这个最长公共前后缀的前缀是S₁~Sₚ₋₁，后缀是Sⱼ₋ₚ₊₂~Sⱼ₋₁。

我们要找S₁~Sⱼ的最长公共前后缀，最优的尝试方向是在已有的最长公共前后缀基础上延长：如果Sⱼ（当前子串的最后一位）和Sₚ（已有最长前缀的下一位）相等，那么新的最长公共前后缀就是S₁~Sₚ和Sⱼ₋ₚ₊₂~Sⱼ，长度为p，对应next[j+1] = p+1。

为什么不比较Sⱼ和Sₚ₋₁？因为Sₚ₋₁对应的是更短的前缀，而我们要找的是最长的公共前后缀。如果连最长的可能延长（匹配Sₚ）都失败了，说明不存在长度为p的公共前后缀，这时候才需要通过j = next[j]回溯到次长的公共前后缀对应的位置，而不是直接去比较更短的前缀位——那样会跳过对最长可能的验证，逻辑上冗余且错误。

二、如何确保逻辑不会错过更长的公共前后缀？ #

以你举的例子为例：假设算法计算得出next[11]对应的最长公共前后缀是S₁~S₄和S₇~S₁₀，这意味着前10位（S₁~S₁₀）的最长公共前后缀长度是4（即next[10] = 5）。

如果存在更长的公共前后缀（比如你说的S₁~S₅和S₆~S₁₀），那前10位的最长公共前后缀长度应该是5，对应的next[10]应该等于6。在计算next[11]时，程序会先比较S₁₀和S₆：如果两者相等，next[11]就会被设为7，对应长度为6的公共前后缀；如果不相等，才会回溯到next[6]继续尝试。

KMP的next数组是递推计算的，每一步的结果都依赖于之前已经确认的最长公共前后缀。如果某个更长的公共前后缀存在，它一定会在之前的步骤中被检测到，对应的next值会被更新，从而在后续计算中优先尝试这个更长的候选。因此算法不会错过任何更长的可能。

内容的提问来源于stack exchange，提问作者NewGreat H