题目回顾
来自《王道2027数据结构考研复习指导》课后习题 4.2.4
KMP算法使用修正后的 next 数组（即 nextval）进行模式匹配。
已知模式串：
S = 'aabaab'
问题：
当主串某个字符与 S 的某个字符失配时，
S 向右滑动的最长距离是多少？
学习背景说明
在哔站的课程中，这几章的课后习题通常是：
前面的题由呼呼老师讲解最后一题由咸鱼老师讲解
而这道题正好是由咸鱼老师讲解的。
由于两位老师的讲解思路略有不同：
一种偏向直观推导（呼呼老师）一种偏向公式总结（咸鱼老师）
这就导致不少同学在切换思路时出现理解断层，感觉“好像听懂了，又好像没完全懂”。
下面我将按照呼呼老师的思路，完整还原这道题的推导过程。
为什么这题容易出错
这道题看似简单，但实际有两个关键难点：
next 和 nextval 容易混淆不清楚滑动距离的计算方式
很多同学会算 nextval，但不知道如何求“滑动距离”，这是失分的主要原因。
手写笔记：
第一步：按步骤求 nextval 数组（核心过程）
这一部分是很多同学最容易“似懂非懂”的地方，下面按照一种更直观的理解方式来推导。
首先记住改进后的 KMP 算法特点：程序能够记住扫描过的所有字符
。
我们假设主串为：
xxxxxxx
模式串：
S = a a b a a b
① 从 nextval[1] 开始
nextval[1] 一定为 0因此主串第 1 位与模式串第 1 位匹配成功（设为 a）从第 2 位开始考虑
② 推导 nextval[2]
模式串第 2 位是 a假设主串第 2 位是 x，与 a 匹配失败所以 nextval[2] = 0，说明没有可复用前缀
关键理解：
程序已经“记住”这个 x 不是 a（KMP 的核心优化）
如果只右移 1 位仍会再次比较这个 x 和 a，结果仍然失败
因此必须直接跳过
所以：
nextval[2] = 0
③ 推导 nextval[3]
现在我们“复原”一种可能情况：
设主串第 2 位是 a（匹配成功）主串第 3 位是 x，与模式串第 3 位 b 失配
但注意：
x 一定不是 b但 x 可能是 a
因此：
模式串可以右移 1 位让模式串第 2 位重新与主串第 3 位对齐
说明存在长度为 2 的可复用前缀
所以：
nextval[3] = 2
④ 后续同理推导
继续按照上述思路：
判断失配字符是否可能匹配前缀位置决定是否可以“少移动”
最终得到：
nextval = [0, 0, 2, 0, 0, 2]
第二步：掌握滑动距离公式
关键公式：
滑动距离 = j - nextval[j]
含义是：
j 表示当前匹配失败的位置nextval[j] 表示可复用的最长前后缀长度两者之差就是模式串需要向右移动的距离
第三步：求最大滑动距离
逐一计算：
j
nextval[j]
滑动距离
1
0
1
2
0
2
3
2
1
4
0
4
5
0
5
6
2
4
最大值为：
5
最终答案
S 向右滑动的最长距离是：
5
核心总结
这类题目的通用解法可以总结为三步：
按逻辑推导 nextval使用公式 j - nextval[j]取最大值
常见错误
将 next 和 nextval 混用不理解 KMP 的“记忆性”忘记使用滑动距离公式没有比较所有位置
结语
这道题本质不难，难的是思路切换。
如果你听完课还是有点模糊，很正常——因为不同老师的讲法确实存在差异。
建议优先掌握一种你最容易理解的方法（比如本文这种推导思路），再去理解公式，会更稳。
当你真正理解了 nextval 和滑动距离的关系，这类题基本不会再出错。
KMP算法中nextval与滑动距离如何本质为？
摘要：题目回顾 来自《王道2027数据结构考研复习指导》课后习题 4.2.4 KMP算法使用修正后的 next 数组（即 nextval）进行模式匹配。 已知模式串： S = 'aabaab' 问题