1. 从一道真题看KMP算法的核心痛点
去年在辅导学生准备统考时，遇到这样一道数据结构真题："给定模式串'abacab'，要求计算其nextval数组，并详细说明KMP匹配过程中模式串的滑动距离如何确定"。这道看似基础的题目，实际正确率不足30%。大多数考生要么死记硬背nextval公式，要么对滑动距离的理解停留在表面。这促使我重新思考：为什么KMP算法教学了这么多年，学生还是难以掌握其精髓？
KMP算法的核心价值在于通过预处理模式串，将暴力匹配的O(mn)时间复杂度优化到O(m+n)。但next数组和nextval数组的区别、滑动距离的计算逻辑，这些恰恰是理解KMP的关键所在。以'abacab'为例，其next数组为[0,0,1,0,1,2]，而nextval数组则是[0,0,1,0,1,0]——这两个数组的差异点正是考生最容易出错的地方。
关键认知：next数组反映的是"最长相同前后缀"，而nextval是next的优化版本，通过避免重复比较进一步提升效率。理解这一点，才能明白为什么有些情况下模式串可以滑动更远。
2. nextval数组的计算原理与实战技巧
2.1 从next到nextval的演进逻辑
常规next数组的计算大家应该不陌生：对于模式串P的每个位置j，next[j]表示P[0...j-1]中最长相等前后缀的长度。以'abacab'为例：
- j=0: 无前缀，next[0]=0（特殊约定）
- j=1: 'a'，next[1]=0
- j=2: 'ab'，next[2]=0
- j=3: 'aba'，最长前后缀'a'，next[3]=1
- j=4: 'abac'，next[4]=0
- j=5: 'abaca'，最长前后缀'a'，next[5]=1
nextval的改进在于：当P[j] == P[next[j]]时，nextval[j] = nextval[next[j]]。这避免了重复比较相同字符。具体计算：
- 初始化nextval[0] = 0
- 对于j=1: P[1]='b' ≠ P[next[1]]=P[0]='a' → nextval[1]=next[1]=0
- j=2: P[2]='a' == P[next[2]]=P[0]='a' → nextval[2]=nextval[nex