如何理解并手动求解KMP算法的nextval数组

KMP算法与next数组的局限

KMP算法是一种高效的字符串匹配算法，其核心思想在于当主串与模式串匹配过程中间出现字符不匹配时，模式串能够根据预先计算好的信息进行“智能”滑动，而不是简单地回退到起始位置重新比较。这个预先计算的信息通常存储在一个名为next的数组中。next数组的每个元素next[j]表示当模式串中第j个字符与主串对应字符失配时，模式串下一次应该与主串当前字符进行比较的字符位置。然而，标准的next数组在某些情况下仍然存在冗余比较。例如，当模式串滑动到新位置后，如果即将参与比较的字符与导致本次失配的字符是相同的，那么这次比较必然也会失败。这种不必要的比较降低了算法效率，而nextval数组正是为了解决这一问题而提出的优化。

从next数组到nextval数组的优化思路

nextval数组是在next数组的基础上进行优化得到的。其优化原理非常直接：如果模式串在位置j发生失配，根据next[j]的值，我们将模式串的指针跳转到位置k（即k = next[j]）。此时，如果模式串中位置j的字符与位置k的字符相同（即 pattern[j] == pattern[k]），那么这次跳转后的比较注定会失败，因为导致上次失配的字符与即将用来比较的字符是同一个。因此，我们可以进一步优化，将nextval[j]的值直接设置为nextval[k]，即进行一次“递归”或“传递”式的修正，使得当字符相同时，模式串能一次性滑动到更远的位置，从而跳过这次必然失败的比较。如果pattern[j] != pattern[k]，那么跳转后的比较是有可能成功的，因此nextval[j]就保持为原来的next值k。这个优化过程显著减少了比较次数，提升了匹配速度。

手动求解next数组的步骤

求解nextval数组的第一步是计算出基础的next数组。手动计算next数组有一套清晰的递推方法。首先定义：next[0] = -1（这是一个约定俗成的起始值，方便编程处理）。假设我们已经知道了next[0], next[1], ..., next[j-1]的值，现在要求next[j]。令k = next[j-1]。比较模式串中第j-1个字符与第k个字符（注意字符串索引通常从0开始）。如果它们相等，那么next[j] = k + 1。如果不相等，则令k = next[k]，继续向前回溯比较，直到k回溯到-1。如果k回溯到-1，则意味着在模式串的前缀中找不到任何能与以j-1结尾的后缀相匹配的更短前缀，此时next[j] = 0。通过这种方式，从j=1开始依次递推，即可完成整个next数组的计算。这个过程的核心是寻找每个位置之前的子串中“最长相等真前缀和真后缀”的长度。

基于next数组计算nextval数组

在得到完整的next数组后，便可以开始计算nextval数组。计算同样采用递推方式。首先，nextval[0]通常也设为-1，因为第一个字符失配时，模式串和主串都需要向后移动一位。然后，对于j从1开始直到模式串末尾，我们根据next[j]的值进行判断。记k = next[j]。比较模式串中第j个字符与第k个字符。如果它们不相等，那么优化不生效，nextval[j] = k。如果它们相等，则说明存在前述的冗余比较，此时nextval[j]的值不应是k，而应该继承nextval[k]的值，即 nextval[j] = nextval[k]。这里使用nextval[k]而非next[k]是为了实现优化的完全传递，避免链式相等字符导致的多次冗余跳转。通过遍历一遍模式串，即可在next数组的基础上快速得到优化后的nextval数组。

一个完整的手动计算实例

假设模式串为“ababaab”。首先计算next数组。根据规则：next[0]=-1。j=1时，比较pattern[0]('a')与pattern[next[0]]（无定义），next[1]=0。j=2时，k=next[1]=0，比较pattern[1]('b')与pattern[0]('a')，不等且k=0，故next[2]=0。j=3时，k=next[2]=0，比较pattern[2]('a')与pattern[0]('a')，相等，故next[3]=1。j=4时，k=next[3]=1，比较pattern[3]('b')与pattern[1]('b')，相等，故next[4]=2。j=5时，k=next[4]=2，比较pattern[4]('a')与pattern[2]('a')，相等，故next[5]=3。j=6时，k=next[5]=3，比较pattern[5]('a')与pattern[3]('b')，不等，令k=next[3]=1，比较pattern[5]('a')与pattern[1]('b')，不等，令k=next[1]=0，比较pattern[5]('a')与pattern[0]('a')，相等，故next[6]=1。得到next数组为[-1, 0, 0, 1, 2, 3, 1]。接下来计算nextval数组。nextval[0]=-1。j=1: k=next[1]=0，pattern[1]('b') != pattern[0]('a')，nextval[1]=0。j=2: k=0，pattern[2]('a') != pattern[0]('a')? 相等？注意是pattern[2]('a')与pattern[0]('a')比较，相等，所以nextval[2]应继承nextval[0]的值-1。j=3: k=1，pattern[3]('b') == pattern[1]('b')，nextval[3]=nextval[1]=0。j=4: k=2，pattern[4]('a') == pattern[2]('a')，nextval[4]=nextval[2]=-1。j=5: k=3，pattern[5]('a') != pattern[3]('b')，nextval[5]=3。j=6: k=1，pattern[6]('b') == pattern[1]('b')，nextval[6]=nextval[1]=0。最终nextval数组为[-1, 0, -1, 0, -1, 3, 0]。对比next数组，可以看到在位置2和4等处的值被优化为-1，使得匹配失败时滑动更高效。