一道KMP统考真题彻底讲透：nextval与滑动距离的本质

题目回顾来自《王道2027数据结构考研复习指导》课后习题 4.2.4KMP算法使用修正后的 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 不是 aKMP 的核心优化如果只右移 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] 表示可复用的最长前后缀长度两者之差就是模式串需要向右移动的距离第三步求最大滑动距离逐一计算jnextval[j]滑动距离101202321404505624最大值为5最终答案S 向右滑动的最长距离是5核心总结这类题目的通用解法可以总结为三步按逻辑推导 nextval使用公式 j - nextval[j]取最大值常见错误将 next 和 nextval 混用不理解 KMP 的“记忆性”忘记使用滑动距离公式没有比较所有位置结语这道题本质不难难的是思路切换。如果你听完课还是有点模糊很正常——因为不同老师的讲法确实存在差异。建议优先掌握一种你最容易理解的方法比如本文这种推导思路再去理解公式会更稳。当你真正理解了 nextval 和滑动距离的关系这类题基本不会再出错。