Vue.js

Appearance

On this page

KMP 算法原理：失配函数与 next 数组 ​

上一章我们看到朴素匹配的问题：失配时丢弃了所有已匹配的信息。KMP 算法的核心思想是利用已匹配部分的结构特征，避免重复比较。

本章聚焦于 KMP 的理论基础——理解 next 数组的含义和手动计算方法。

问题回顾 ​

T: A B A B A B A B C
P: A B A B C
         ↑ 位置 4 失配

朴素算法：回退到 T[1], P[0] 重新开始
问题：T[0..3] = "ABAB" 已经匹配成功，这包含有用的信息！

KMP 问的是：能否利用已匹配的 "ABAB" 来跳过一些不必要的比较？

前缀与后缀 ​

要理解 KMP，首先要明确两个概念：

前缀（Prefix）：字符串除最后一个字符外的所有起始子串 后缀（Suffix）：字符串除第一个字符外的所有结尾子串

以字符串 "ABAB" 为例：

前缀: "A", "AB", "ABA"
后缀: "B", "AB", "BAB"

注意：前缀和后缀都不包括字符串本身

最长公共前后缀：既是前缀又是后缀的最长子串。

字符串: A B A B
        ├──┤        前缀 "AB"
            ├──┤    后缀 "AB"

公共前后缀: "AB"
最长公共前后缀长度: 2

为什么这个概念重要？因为它告诉我们失配后可以跳到哪里继续比较。

next 数组的定义 ​

next[j] 表示模式串 P[0..j-1]（前 j 个字符组成的子串）的最长公共前后缀长度。

换一种说法：当 P[j] 与主串某个字符失配时，模式串应该跳到位置 next[j] 继续比较。

计算示例 ​

以 P = "ABABC" 为例：

j=0: ""       → 空串，next[0] = 0
j=1: "A"      → 长度为 1，无真前后缀，next[1] = 0
j=2: "AB"     → 前缀 "A"，后缀 "B"，无公共，next[2] = 0
j=3: "ABA"    → 前缀 "A","AB"，后缀 "A","BA"，公共 "A"，next[3] = 1
j=4: "ABAB"   → 前缀 "A","AB","ABA"，后缀 "B","AB","BAB"，公共 "AB"，next[4] = 2

next = [0, 0, 0, 1, 2]

为什么 next 数组有用？ ​

这是理解 KMP 的关键。让我们仔细分析：

T: ... X X X X X X X X ...
       |←── 已匹配 ──→|
P:     A B A B C
       0 1 2 3 4
             ↑ 位置 4 失配

当 P[4] = 'C' 与 T 的某个字符失配时：

  • P[0..3] = "ABAB" 已经与 T 的对应部分匹配
  • "ABAB" 的最长公共前后缀是 "AB"（长度 2）
  • 这意味着 P[0..1] = "AB" = P[2..3]

所以：

T: ... X X X X X X X X ...
           |←─ 已知相等 ─→|
P:         A B A B C
           0 1 2 3 4
           ↑ 从位置 2 继续比较！

因为 T 的后两个字符等于 P 的后两个字符 "AB"，而 P 的前两个字符也是 "AB"，所以 T 的后两个字符必然等于 P 的前两个字符。我们可以跳过这两个位置的比较，直接从 P[2] 开始！

这就是 KMP 的精髓：利用模式串自身的结构特征，失配时智能跳转。

手动计算练习 ​

掌握 next 数组的最好方法是多做练习。

练习 1：P = "AAAB" ​

j=0: ""      → 0
j=1: "A"     → 0
j=2: "AA"    → 前缀 "A"，后缀 "A"，公共 "A" → 1
j=3: "AAA"   → 前缀 "A","AA"，后缀 "A","AA"，公共 "AA" → 2

next = [0, 0, 1, 2]

练习 2：P = "ABCDABD" ​

j=0: ""        → 0
j=1: "A"       → 0
j=2: "AB"      → 0
j=3: "ABC"     → 0
j=4: "ABCD"    → 0
j=5: "ABCDA"   → 前缀 "A"，后缀 "A"，公共 "A" → 1
j=6: "ABCDAB"  → 前缀有 "AB"，后缀有 "AB"，公共 "AB" → 2

next = [0, 0, 0, 0, 0, 1, 2]

练习 3：P = "ABABCABAB" ​

j=0: ""          → 0
j=1: "A"         → 0
j=2: "AB"        → 0
j=3: "ABA"       → "A" = "A" → 1
j=4: "ABAB"      → "AB" = "AB" → 2
j=5: "ABABC"     → 无公共 → 0
j=6: "ABABCA"    → "A" = "A" → 1
j=7: "ABABCAB"   → "AB" = "AB" → 2
j=8: "ABABCABA"  → "ABA" = "ABA" → 3

next = [0, 0, 0, 1, 2, 0, 1, 2, 3]

思考：什么样的模式串 next 数组全为 0？ ​

答案：每个字符都不相同的字符串，如 "ABCDE"。

因为没有重复字符，就不可能有相同的前缀和后缀。

next 数组的另一种理解 ​

next[j] 有两层含义：

  1. 长度含义：P[0..j-1] 的最长公共前后缀的长度
  2. 位置含义：当 P[j] 失配时，下一个要比较的位置

这两层含义在数值上是相等的。因为如果最长公共前后缀长度是 k，那么 P[0..k-1] 已经与主串对应部分匹配，下一步应该比较 P[k]。

失配时的跳转规则：
j = next[j]

不同的 next 数组定义 ​

在不同的教材和实现中，next 数组的定义可能略有不同：

版本 1（本书使用）：

  • next[0] = 0
  • next[j] = P[0..j-1] 的最长公共前后缀长度

版本 2（传统教材常用）：

  • next[0] = -1（特殊标记）
  • next[j] = P[0..j-1] 的最长公共前后缀长度

两种定义本质相同，只是边界处理略有差异。理解核心思想后，适应不同实现并不难。

本章小结 ​

KMP 算法的理论基础是最长公共前后缀：

  1. next[j] 记录 P[0..j-1] 的最长公共前后缀长度
  2. 失配时，根据 next 数组跳转，避免重复比较
  3. 这利用了模式串自身的结构特征

手动计算 next 数组是理解 KMP 的关键。确保你能熟练计算任意模式串的 next 数组后，再进入下一章学习如何高效构建 next 数组以及完整的 KMP 实现。

练习：

  1. 计算 "AABAAAB" 的 next 数组
  2. 计算 "ABCABDABCABC" 的 next 数组

在 GitHub 上编辑此页