考研笔记

KMP 算法及其优化

三道统考真题，考的都是手工模拟：2015 问失配后指针的值，2019 数比较次数，2024 求右滑的最长距离。 教材【复习提示】：「重点掌握 KMP 匹配算法的原理及 next 数组的推理过程，手工求 next 数组可以先计算出部分匹配值表然后变形，或根据公式来求解。了解 nextval 数组的求解方法。」next 与 nextval 的两个教材例和逐项验算收在 速查：KMP 的 next 与 nextval，本页补部分匹配值法、比较次数的数法和真题的下标口径。

机制

4.2.2 原理：部分匹配值

  • 前缀：除最后一个字符外，字符串的所有头部子串。
  • 后缀：除第一个字符外，字符串的所有尾部子串。
  • 部分匹配值（PM）：字符串的前缀和后缀的最长相等前后缀长度。

以 'ababa' 为例：'a' 为 0；'ab' 为 0；'aba' 的前缀 与后缀 交集为 ，为 1；'abab' 为 2（ab）；'ababa' 的交集为 ，取最长，为 3。所以 'ababa' 的部分匹配值为 00123。

失配时，已匹配的那段字符就是模式串的某个前缀。若这段前缀的首尾有重合（相等的前后缀），就把模式串右滑到首尾对齐的位置，主串指针 无须回溯：右滑位数已匹配的字符数对应的部分匹配值教材例：主串 'ababcabcacbab'，模式串 'abcac'，PM 为 00010。第一趟在第 3 个字符失配，已匹配 2 个，最后一个匹配字符的 PM 为 0，右滑 位；第二趟在第 5 个字符失配，已匹配 4 个（'abca'），PM 为 1，右滑 位；第三趟匹配成功。右滑位数只与模式串本身有关，与主串无关。

从 PM 表到 next 数组

实际匹配时模式串不会滑动，变化的是指针。定义 next[j]：模式串的第 个字符失配时，跳到 next[j] 位置继续比较。第 个字符失配时已匹配 个字符，于是右滑位数把 PM 表右移一位、整体加 1，就得到 next 数组。 右移后第一位空缺用 0 填充（第一个字符失配时，主串指针和模式串指针同步右移一位）；最后一个元素的 PM 值溢出，舍去。next[1]=0、next[2]=1 固定不变。

教材注意框：「上述 KMP 算法的举例中，都假设串的编号是从 1 开始的；若串的编号是从 0 开始的，则 next 数组需要整体减 1。」

*next 的递推（标 *）

设 next[j]=k，求 next[j+1]：

  • 若 ，则 next[j+1]=k+1，即 next[j+1]=next[j]+1。
  • 若 ，令 继续比较 与 ，直到相等（next[j+1]=k+1），或 （next[j+1]=1）。

教材图 4.4：模式串 'abaabcaba' 已求得前 6 个 next 值为 0,1,1,2,2,3。求 next[7]：next[6]=3，；比较 与 ，仍不等，而 next[1]=0，所以 next[7]=1。之后 得 next[8]=2， 得 next[9]=3。

KMP 匹配算法

与简单模式匹配形式相似，不同之处仅在于失配时指针 不变，指针 退回到 next[j]；且当 为 0 时， 和 同时加 1。完整代码见速查表。

  • 时间复杂度 ；普通模式匹配是 ，但一般情况下实际执行时间近似 ，因此至今仍被采用。
  • KMP 仅在主串与子串有很多「部分匹配」时才显得比普通算法快，其主要优点是主串不回溯。

4.2.3 nextval：进一步优化（2024 命题追踪）

不应该出现 。 当 时，下次必然拿 跟 比较；若二者相等，这次比较必然失配，毫无意义。修正方法：若 ，就把 next[j] 修正为 next[next[j]]，直至两者不相等为止，修正后的数组命名为 nextval。匹配算法不变。

手算模板

① 求 next：先写 PM，右移一位，整体加 1。 例：'ababaaababaa'（4.2.4 第 6 题）的 PM 为 0,0,1,2,3,1,1,2,3,4,5,6，next 为 0,1,1,2,3,4,2,2,3,4,5,6。

② 数比较次数：每一趟从起点比到失配（失配的那次也算）或比到模式串末尾。 时 、 同时加 1，不算比较。

③ 右滑距离 （用 nextval 时为 ）。这个差值与下标从 0 还是从 1 起无关，两套口径算出来一样。

口径差异：真题的下标口径不固定，王道按题目「灵活应变」

教材正文以位序从 1、next[1]=0 为准，但三道统考真题的王道解析都改用了位序从 0、next[0]=-1：2015 的题干写「 时 」，解析第一句就是「可知题中的主串和模式串的位序都是从 0 开始的（要注意灵活应变）」；2019、2024 的解析也写「假设位序从 0 开始」。 4.2.4 第 7 题的四个选项干脆都以 开头，答案解析的结论是「next 数组是否整体加 1 都正确，需根据题意具体分析」。 做法：先看题干给出的下标（或选项的首项）定口径，再写 next。比较次数和右滑距离不受口径影响，可以放心按自己熟悉的口径算。 这一条修正了 速查表开头「按算竞口径写整张表作废」的说法：只有题目明确要求写出 next 数组时，口径才决定对错。

边界

说法判断说明
「部分匹配值是前缀和后缀的公共元素个数」❌是最长相等前后缀的长度。'ababa' 的公共元素有 、 两个，PM 取 3
「前缀包括整个字符串」❌前缀是除最后一个字符外的头部子串
「next[j]=PM[j]+1」❌是 ：PM 表要先右移一位
「右滑位数 = 已匹配的字符数」❌还要减去对应的部分匹配值
「KMP 中主串指针可能变小」❌不会变小，主串不回溯
「失配时 的变化是 i=i+1」❌ 不变；只有 时 、 同时加 1
「KMP 在任何情况下都比简单匹配快得多」❌只在部分匹配多时才明显快
「nextval 需要重新设计匹配算法」❌匹配算法不变
「408 真题的 next 一律从 1 开始」❌2015、2019、2024 的王道解析都按位序从 0 算
「比较次数只数相等的比较」❌失配的比较也算一次

错题复盘：2015 第一次失配后 和 的值

'abaabaabacacaabaabcc'， 'abaabc'，第一次失配时 （位序从 0 起），下次开始匹配时 ，（选 C）。 的 next（从 0 起）为 。失配时主串指针不动， 退到 next[5]=2。 选项 B（）和 D（）分别错在「 回到开头」和「 后移一位」，这正是简单匹配和 KMP 的两处区别。

错题复盘：2019 数比较次数

主串 'abaabaabcabaabc'，模式串 'abaabc'，匹配成功为止共比较 10 次（选 B）。 第一趟连续比较 6 次，在模式串的 5 号位和主串的 5 号位失配（位序从 0 起）；模式串下一个比较位置为 next[5]=2，第二趟从模式串 2 号位与主串 5 号位比起，到模式串 5 号位与主串 8 号位匹配，比较 4 次。。 若按简单模式匹配数（失配后主串回溯、模式串从头比），共比较 15 次，正是干扰项 D（已用程序复核）。

错题复盘：2024 修正后的 next 数组，右滑的最长距离

模式串 'aabaab'，使用 nextval 时，右滑的最长距离是 5（选 A）。 位序从 0 起：next 为 ，nextval 为 ；右滑距离 依次为 ，最大值 5 出现在 。 处 a，next[4]=1， a 与之相等；再退到 next[1]=0， a 仍相等，最终 nextval[4]=-1。nextval 可能连退两级，右滑距离因此比用 next 时更大。

错题复盘： next 与 nextval 的比较次数（4.2.4 第 8、9 题）

主串 'aabaaaba'，模式串 'aaab'。用 next（0,1,2,3）共比较 次；用 nextval（0,0,0,3）共比较 次。 第一趟在 b、 a 处失配。next 让 、 依次再跟 比，两次都必然失败；nextval[3]=0 直接跳过这两次。这就是 4.2.3 优化的全部内容。

考点

  • 部分匹配值的定义；右滑位数 = 已匹配字符数 − 部分匹配值。
  • next = PM 右移一位再加 1；next[1]=0、next[2]=1。
  • 失配时 不变、； 时同时加 1（2015）。
  • 比较次数（2019）与右滑距离（2024）的手工模拟。
  • nextval 的修正规则；匹配算法不变。
  • 真题下标口径不固定，先看题干。

链接

反向链接