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

题目回顾

源自《王道2027数据结构考研复习指导》课后习题，4.2.4这一题目。

KMP 算法，运用修正过后的 next 数组，也就是 nextval，来开展模式匹配。

已知模式串：

S = 'aabaab'

问题：

当主串某个字符与 S 的某个字符失配时，

S 向右滑动的最长距离是多少？

学习背景说明

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

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

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

那便致使好些同学于转换思路之际呈现出理解上的间断，觉得“仿佛是听懂了，然而又仿佛并非全然听懂”。

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

为什么这题容易出错

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

接着的那个，与紧接着的值，容易弄混，搞不明白滑动距离的计算办法，计算方式。

不少同学能够算出nextval，然而不清楚怎样去求“滑动距离”，这可是导致失分的主要缘由句号。

手写笔记：

第一步：按步骤求 nextval 数组（核心过程）

许多同学在这一部分极易陷入听起来好像懂了，实际上又没完全明白的状况，接下来依据一种更为直观的理解办法去进行推导。

首先，记住，改进之后的，KMP 算法，所具备的特点，那就是，程序，能够，记住，扫描经历过的，所有字符。

我们假设主串为：

xxxxxxx

模式串：

S = a a b a a b

① 从 nextval 开始② 推导 nextval

关键理解：

程序已经“记住”这个 x 不是 a（KMP 的核心优化）

倘若仅仅进行右移一位的操作，那么还会再度对这个x以及a展开比较，而其结果依旧是失败。

因此必须直接跳过

所以：

nextval[2] = 0

③ 推导 nextval

现在我们“复原”一种可能情况：

但注意：

因此：

说明存在长度为 2 的可复用前缀

所以：

nextval[3] = 2

④ 后续同理推导

继续按照上述思路：

最终得到：

nextval = [0, 0, 2, 0, 0, 2]

第二步：掌握滑动距离公式

关键公式：

滑动距离 = j - nextval[j]

含义是：

第三步：求最大滑动距离

逐一计算：

| j | nextval | 滑动距离 |

| - | ---------- | ---- |

| 1 | 0| 1 |

| 2 | 0| 2 |

| 3 | 2| 1 |

| 4 | 0| 4 |

| 5 | 0| 5 |

| 6 | 2| 4 |

最大值为：

5

最终答案

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

5

核心总结

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

依逻辑进行推导，nextval运用公式，其中j减去nextval所得结果取为最大值，这是常见的错误情况，结语由此得出。

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

要是你听完了课程之后，仍旧略微有些模糊不清，这是十分正常的情况，毕竟不同授课老师所采取的讲授方式的确会存在着差异。

提出建议，要优先把控住一类你最为容易领会的方式，就好比本文之中这种推导的思路，之后再着手去理解公式，如此会更加稳妥。

当你切实领会了nextval与滑动距离之间的关联，这种类型的题目基本上就不会再度出现错误了。

本文由mdnice多平台发布

相关标签： # KMP算法 # nextval数组 # 滑动距离 # 模式匹配 # 数据结构