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

每日一首歌：

题目回顾

来自《王道2027数据结构考研复习指导》课后习题 4.2.4

KMP算法使用修正后的 next 数组（即 nextval）进行模式匹配。

已知模式串：

S = 'aabaab'

问题：

当主串某个字符与 S 的某个字符失配时， S 向右滑动的最长距离是多少？

学习背景说明

在哔站的课程中，这几章的课后习题通常是：

• 前面的题由呼呼老师讲解
• 最后一题由咸鱼老师讲解

而这道题正好是由咸鱼老师讲解的。

由于两位老师的讲解思路略有不同：

• 一种偏向直观推导（呼呼老师）
• 一种偏向公式总结（咸鱼老师）

这就导致不少同学在切换思路时出现理解断层，感觉“好像听懂了，又好像没完全懂”。

下面我将按照呼呼老师的思路，完整还原这道题的推导过程。

为什么这题容易出错

这道题看似简单，但实际有两个关键难点：

1. next 和 nextval 容易混淆
2. 不清楚滑动距离的计算方式

很多同学会算 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] 表示可复用的最长前后缀长度
• 两者之差就是模式串需要向右移动的距离

第三步：求最大滑动距离

逐一计算：

最大值为：

5

最终答案

S 向右滑动的最长距离是：

5

核心总结

这类题目的通用解法可以总结为三步：

1. 按逻辑推导 nextval
2. 使用公式 j - nextval[j]
3. 取最大值

常见错误

• 将 next 和 nextval 混用
• 不理解 KMP 的“记忆性”
• 忘记使用滑动距离公式
• 没有比较所有位置

结语

这道题本质不难，难的是思路切换。

如果你听完课还是有点模糊，很正常——因为不同老师的讲法确实存在差异。

建议优先掌握一种你最容易理解的方法（比如本文这种推导思路），再去理解公式，会更稳。

当你真正理解了 nextval 和滑动距离的关系，这类题基本不会再出错。