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