KMP算法真题详解：next与nextval数组滑动距离一次讲透

说到 KMP很多备考数据结构统考的考生都能把那张“手算 next / nextval 的方法”背下来什么最长相等前后缀加一、什么字符相同就往前跳。可一旦真拿到一道题问“此时模式串向右滑动多少位”不少人就卡住了。我当年也卡过后来是拿一道真题反复推了三遍才彻底想明白所谓“滑动距离”到底在滑什么、为什么 nextval 能比 next 滑得更远。这篇文章我就用一道很典型的统考风格真题把这套东西从头到尾掰开揉碎讲清楚连带你考场上的易错点一起搞定。这道题问的是给定模式串 (p abaabcac)求它的 next 数组和 nextval 数组并且当匹配过程中模式串第 5 个字符处发生失配时使用 nextval 数组时模式串应向右滑动的距离是多少。乍看只是常规计算题但它把 KMP 的两个核心概念拴在了一起一个是数组怎么算一个是失配后模式串到底怎么动。能把滑动距离的原理讲明白KMP 基本就算入门了。1. 先从真题视角看这类题究竟在考什么1.1 一道高度还原的统考风格真题下面是这类题目在考卷上最常见的形态代号和措辞我按教学场景稍作整理但考法还原度很高已知模式串 (p abaabcac)采用 KMP 算法进行字符串匹配下标从 1 开始。(1) 写出模式串的 next 数组和 nextval 数组(2) 若某次匹配在模式串第 5 个字符处失配主串指针不动使用 nextval 数组模式串向右滑动的距离是多少并说明为什么。这道题把 KMP 中两个最容易被混淆的东西一起考了你既要能算出两个数组又要能解释数组在匹配过程中对应的是什么动作。很多同学第一问能拿分第二问就靠蒙因为平时只背计算口诀没有把“j 回退到 nextval[j]”和“模式串向右滑动”联系起来。1.2 为什么这样一道题能难住一多半人我见过不少备考者他们能流利地说出“nextval[j] 是 next[j] 的改进版”但你要问他“改进”在哪里他就说不清了。常见的错误有三种第一种把 next 和 nextval 当成两个独立表算完就完了压根没想过它们对应的是失配后 j 要跳去的位置。于是第二问直接写“滑动 5 - 2 3 位”这其实是拿 next 数组算的不是 nextval。第二种知道要用 nextval但搞不清滑动距离到底是 (j - nextval[j]) 还是 (nextval[j])。有的同学写成“向右滑动 nextval[j] 位”也就是 1 位方向直接反了。第三种对 nextval 的链式回退规则不理解算到一半就乱套。比如计算 nextval[5] 时明明确认了 (p[5] p[next[5]])却不知道下一步要取 nextval[next[5]]而不是直接照抄 next[5]。这道题的意义就在于它逼你把“数组值”和“物理滑动”一一对应起来。只要能讲清为什么失配发生在第 5 个字符、为什么 nextval[5] 1、为什么滑动距离是 4 而不是 3那么 KMP 的核心动作你就真的拿下了。2. 先把 next 数组的手算逻辑彻底拆干净2.1 next 数组的定义不是直觉上的“最长相等前后缀加一”很多教材给出的是这个说法对于模式串 (p[1..m])next[j] 表示当 (p[j]) 与主串失配时j 应该回退到的位置。具体计算时则是看 (p[1..j-1]) 这一段字符串的最长相等前后缀长度再加上 1。这里有个很容易忽略的边界next[1] 和 next[2]。按统考常用的下标从 1 开始的约定next[1] 0next[2] 1。理由很简单当第一个字符就失配时模式串没法再往前退了所以用 0 作为哨兵第二个字符失配时前面只匹配过一个字符而这个字符的最长相等前后缀长度是 0所以 next[2] 0 1 1。为了不让大家死记口号我建议别急着背“加一”而是先看实际例子。以 (p abaabcac) 为例我们可以先把每个位置 j 对应的“已匹配前缀”写出来j已匹配部分 (p[1..j-1])最长相等真前后缀长度next[j]1空-02a013ab014aba1前缀 a 后缀 a25abaa1前缀 a 后缀 a26abaab2前缀 ab 后缀 ab37abaabc018abaabca1前缀 a 后缀 a2所以第一问的 next 数组是[ next [0, 1, 1, 2, 2, 3, 1, 2] ]注意这里的数组元素是从下标 1 开始陈列的实际写成序列就是 0、1、1、2、2、3、1、2。2.2 手算时最容易出错的两个位置位置 4 和位置 6 是这道题里最容易算错的地方我把它们的判断逻辑单独拿出来讲。先看位置 4。已匹配部分是 (p[1..3] aba)要找的是它的最长相等真前后缀。“真前后缀”的意思是不能取整个字符串本身。对 aba 来说前缀 a 和后缀 a 相等长度是 1前缀 ab 和后缀 ba 不相等所以最长相等真前后缀长度就是 1next[4] 1 1 2。再看位置 6。已匹配部分是 (p[1..5] abaab)。这里前缀 ab 等于后缀 ab长度是 2。有些人会把前缀 aba 和后缀 aab 拿去比结果发现不相等就慌了其实只需要看最长的那个候选是否成立不成立再往下缩短就行。复杂度并不高关键是别跳步。2.3 为什么统考爱用 abaabcac 这个串这个模式串设计得很巧妙。它里面有重复出现的单字符 a有两次字符对 ab有中间断开的地方几乎覆盖了 next 计算的所有典型情况。比如 j 3 时最长相等前后缀长度为 0j 6 时长度为 2j 7 时又掉回 0。你要是能把这一串算熟练考试里遇到类似的模式串基本就不会再犯原则性错误。而且这个串也方便我们后面讲 nextval。因为它并不是连续重复字符那种看一眼就懂的极端模式而是穿插了不同字符的“正常模式”反而更能考察你对规则的理解而不是对对称性的直觉。3. nextval 的真面目把已知会失败的比较提前消灭3.1 nextval 的递推规则一句话说清nextval 的递推规则是[ nextval[1] 0 ]对于 (j \ge 2)先看 (p[j]) 和 (p[next[j]]) 是否相等若不相等(nextval[j] next[j])若相等(nextval[j] nextval[next[j]])。很多同学背错了后半句以为相等时 nextval 就等于 nextval[j-1]这是大错特错。正确做法是(j) 要回溯到 (next[j]) 那个位置再看那个位置的 nextval 值。为什么这么定义因为 next[j] 指示的是失配后 j 要去的位置但如果 (p[j]) 恰好和 (p[next[j]]) 是同一个字符那么就算你跳过去了下一次比较拿同一个字符去对主串里那个已经失配的字符结果仍然是失配。与其做一次注定失败的比较不如继续顺着 nextval 跳到更前面跳过这次无效劳动。这正是 nextval 的核心思想它不是在改写 next 数组而是在回收“已经能确定会失败”的比较机会。3.2 逐位演算 abaabcac 的 nextval我从头到尾算一遍大家对着表看jp[j]next[j]p[next[j]]是否相等nextval[j]1a0--02b1a否13a1a是nextval[1] 04a2b否25b2b是nextval[2] 16c3a否37a1a是nextval[1] 08c2b否2因此[ nextval [0, 1, 0, 2, 1, 3, 0, 2] ]细心的同学会发现位置 4 和位置 5 的运转逻辑特别能说明问题。位置 4 中 (p[4] a)而 (p[next[4]] p[2] b)字符不同所以 nextval[4] 直接采用 next[4] 2。而位置 5 中 (p[5] b)(p[next[5]] p[2] b)字符相同所以不能停在 next[5] 2 这里而是继续跳到 nextval[2] 1最终 nextval[5] 1。3.3 链式回退是 nextval 计算中的隐形陷阱实际手算时最阴险的坑就是链式回退不是一次就结束的。比如某个位置 (p[j]) 与 (p[next[j]]) 相等你跳到 nextval[next[j]]发现那里的字符仍然有可能继续满足相等条件这时候得继续往前跳吗答案是不需要你手工一层层展开到最底层。因为 nextval 数组是按 j 从小到大的顺序计算的(nextval[next[j]]) 这个值在你算到 (j) 之前就已经是最终定稿的版本了它内部已经包含了多级跳转的压缩。比如上面位置 5 用到 nextval[2] 1而 nextval[2] 本身就是从 next[2] 1 再判断后得到的它已经是最终结果不会再继续跳。这个性质给手算带来了很大方便你只需要判断一层相等关系然后直接查表引用之前算好的 nextval 值即可。3.4 nextval 为什么可能比 next 更小从数值上看nextval[j] 通常不等于 next[j]而且往往是更小的值甚至可能变成 0。有人会疑惑nextval 既然是“优化”为什么数值还变小了别忘了数组值是描述“失配后跳回的位置”。值越小说明模式串回退得越狠对应到物理动作上就是模式串整体向右滑动的距离越大。所以 nextval[j] 更小并不代表退化恰恰代表优化——它把那些无谓的重复比较跳过去了。至此我们还剩一个关键问题滑动距离到底怎么从数组值换算出来我放到下一节专门讲。4. 滑动距离的本质主串指针不动模式串靠什么找回进度4.1 从“j 回退”到“模式串右移”的等价换算KMP 的标准执行流程是匹配到 (i) 位置和 (j) 位置时若失配主串指针 (i) 不动模式串指针 (j) 回退为 (next[j])或 (nextval[j])。但考题如果问“模式串向右滑动多少位”它问的其实是另一个等价量。要知道主串当前位置 (i) 与模式串当前比较位置 (j) 是对齐的。失配后 (j) 变成了 (new_j)那么原本 (p[j]) 所占的那个主串位置就轮到 (p[new_j]) 来对齐。从模式串整体来看相当于模式串向右移动了 (j - new_j) 个位置。所以用 next 数组时滑动距离是 (j - next[j])用 nextval 数组时滑动距离是 (j - nextval[j])。这里必须强调滑动距离不是 next[j]也不是 nextval[j]而是两者之间的差。这个点几乎年年有人错。4.2 回到真题第 5 个字符失配nextval 为什么能滑 4 位现在我们把第 5 个字符失配的场景完整演一遍。设某次匹配时主串中已成功匹配了前 4 个字符 (p[1..4] abaa)而第 5 个字符处主串对应的字符我们记为 (\alpha)不等于模式串的 (p[5] b)。换句话说失配点是主串第 (i) 个位置、模式串第 5 个位置。如果只考虑 next 数组next[5] 2那么 j 回退到 2滑动距离是 5 - 2 3。可我们已知第 5 个位置主串字符 (\alpha) 不是 b。而模式串第 2 个字符恰恰也是 b所以 j 回退到 2 之后拿 (p[2] b) 去和 (\alpha) 比较结果必然是再次失配。既然这一趟注定白比较还不如直接利用 nextval 把它跳掉。nextval[5] 1所以使用 nextval 数组时j 直接回退到 1滑动距离是 5 - 1 4。模式串一下多滑了 1 位跳过了拿 b 再比一次的无用功。在考试里第二问的答案写“滑动距离 4 位”还不够最好补一句因为 nextval[5] 1且失配后主串指针不动模式串向右移动 5 - 1 4 位。4.3 极端例子连续重复字符下一次滑动能从 1 变成 5只看 abaabcac 这个例子nextval 带来的滑动优势感还不够直观。我再给一个更极端的模式串(p aaaaab)长度 6。手算它的 nextjp[1..j-1]next[j]1-02a13aa24aaa35aaaa46aaaaa5再算 nextval由于 (p[2], p[3], p[4], p[5]) 都等于前缀 a而 next[2..5] 指向的也都是 a所以这几位会一路链回[ nextval [0, 0, 0, 0, 0, 5] ]这时候假如失配发生在模式串第 5 个字符处用 next 数组只滑 5 - 4 1 位而用 nextval 数组直接滑 5 - 0 5 位。在实际匹配中比如主串是 ...aaaac...模式串滑 1 位后(p[4] a) 对上的仍是那个 c还要再确认一次失配然后接着滑 1 位再确认一次……等于连续做 4 次注定失败的比较。而 nextval 一步把模式串整段滑过去让 (p[1] a) 直接对接失配字符。省掉的不是 1 次比较而是一整段无效比较。4.4 为什么说滑动距离的本质是“安全跳过量”如果把暴力匹配比作逐格试探KMP 每次失配后的滑动距离就是模式串整体向右挪动的格子数。这个格子数不是越大越好而是要在“绝对不遗漏可能的匹配起点”的前提下尽量大。(next[j]) 给出的安全跳过量基于已匹配前缀的自重叠关系(nextval[j]) 则在它的基础上进一步排除了“就算跳过去也会立刻失配”的情况所以安全跳过量进一步增大。这就是为什么 nextval 数组能在时间上继续优化 KMP——它让模式串更敢大步往前走。5. 考场实战这类题的易错点与验算方法5.1 下标从 1 还是从 0 开始先看题再动手统考数据结构教材里字符串通常从下标 1 开始next[1] 0、next[2] 1。但有些习题或自命题会采用下标从 0 开始此时 next 数组的初值和递推写法都会变常见定义变成 next[0] -1next[1] 0 之类。同一个模式串两套体系算出的数组序列完全不同不要混用。我的建议是拿到题先看有没有给出“下标从 1 开始”的说明。如果有就按本文这套规则如果没说明默认按你平时教材的习惯走。写答案时最好顺手标一句“以下按字符串下标从 1 开始计”既提醒自己也能让阅卷时印象分好一点。5.2 nextval 的链式引用怪圈算到一半发现引用还没算按 j 从小到大递推 nextval 时有一个细节容易让人怀疑自己算错当 (p[j] p[next[j]]) 时要引用 (nextval[next[j]])而这个 nextval 值往往已经在前面算好了。因为 next[j] 一定小于 j所以这个引用总是安全的不会出现“引用了一个尚未计算的值”的尴尬。这背后其实是一种动态规划思想后一个位置的优化结果依赖于前面位置已经计算好的优化结果。你不需要每次从头推导查表就行。一旦理解了这个顺序性手算速度能快不少。5.3 答题时最容易扣分的两种措辞第一当题目明确问“使用 nextval 数组”时滑动距离必须写 (j - nextval[j])。有些同学心里算对了但写成“滑动 nextval[j] 位”这就等于直接把数组值当成滑动量会扣分。第二如果你用了 next 和 nextval 两套数组分别算滑动距离一定要分清楚不同失配位置对应不同结果。同样是模式串 abaabcac第 5 位失配滑 4 位第 6 位失配呢(nextval[6] 3)滑动距离就是 6 - 3 3。第 7 位失配呢(nextval[7] 0)滑动距离 7 位。可见答案因失配位置而变不能笼统说“这个模式串滑 N 位”。5.4 一个超实用的验算方法随手拉一条主串草稿备考时我建议你做完这类题后不要直接看答案而是自己写一条主串把匹配过程一步步画出来。以真题第二问为例你可以假设主串的失配位置字符为某个非 b 字符然后模拟用 nextj 先跳到 2拿 b 去比再失配j 再跳整体多比了一次用 nextvalj 直接到 1少了一次无效比较。画完这遍草稿你会深刻理解“滑动距离”不是抽象公式而是模式串在文本上的实际位移。这个方法在考场上可能没时间完整做但平时练习的时候做上三五个考试基本不会再错。我个人备考时的体会是KMP 难不在公式难在把数组值、指针回退和模式串位移这三层概念扭到一起。只要你肯动手拿任意一个模式串算完 next 和 nextval再拉一条主串把失配过程画一遍最多三道题就能彻底打通。记住这句话nextval 不是为了让数组更小而是为了让模式串在失配后能理直气壮地跨过那些一定走不通的路。