KMP 模式串匹配算法讲解

什么是模式串匹配

想象一下，你正在浩如烟海的文本海洋中寻找一根特定的“针”——这就是模式串匹配 (Pattern Matching) 的核心任务。
具体来说，我们有两个字符串：

• 文本串：一个非常长的字符串，是我们的主要处理对象。例如，一篇数万字的论文、一段基因序列、或者服务器上滚动的日志文件。我们将其记为 T，其长度为 n，字符从 T[1] 到 T[n]。
  
• 模式串：一个相对较短的字符串，是我们希望在文本串中寻找的目标。例如，一个特定的关键词、一个已知的病毒基因片段、或者一条特定的错误代码。我们将其记为 P，其长度为 m，字符从 P[1] 到 P[m]。
  

模式串匹配的目标就是，高效地回答以下问题：

• 存在性：模式串 P 是否在文本串 T 中出现过？
  
• 计数：如果出现过，一共出现了多少次？
  
• 定位：每次出现的起始位置在哪里？
  

这个技术应用极其广泛，举个现实的例子：作为一名社区管理员，你需要处理用户发布的帖子。模式串匹配可以帮助你：

• 自动审核：快速扫描帖子，查找是否包含“脏字”或“违禁词”（模式串）。
  
• 量化惩罚：通过统计违禁词的出现次数，来决定对用户的惩罚等级。
  
• 内容净化：精确定位到每个违禁词的出现位置，并自动将其替换为“*”，实现内容屏蔽。
  

在数据量巨大的今天，匹配算法的效率至关重要。一个糟糕的算法可能会让用户等待数秒甚至数分钟，而一个优秀的算法则能在瞬间完成任务。KMP 算法，就是这其中的佼佼者。
朴素匹配算法的瓶颈

在深入 KMP 的精妙之处前，我们先来回顾最直观的匹配方法——朴素匹配算法（也称暴力匹配算法）。
它的思路简单粗暴：

• 从文本串的第 i 个位置开始（i 从 1 到 n-m+1），将模式串 P 与文本串的子串 T[i...i+m-1] 进行逐位比较。
  
• 如果所有 m 个字符都匹配成功，就记录下起始位置 i，完成一次查找。
  
• 如果在比较过程中，发现某一位字符不匹配（我们称之为“失配”），就立即停止本次比较。
  
• i 增加 1，回到第 1 步，开始新一轮的比较。
  

让我们看一个例子：

• 文本串 T: ABCABCABD
  
• 模式串 P: ABCABD
  

1. i=1: T[1...6] vs P[1...6]
2. T: A B C A B C A B D
3. P: A B C A B D        (在第6位, T[6] 'C' 与 P[6] 'D' 失配)
5.    ↓ 失配后，i 增加 1，从 i=2 开始重新比较
7. i=2: T[2...7] vs P[1...6]
8. T: A B C A B C A B D
9. P:   A B C A B D      (在第1位, T[2] 'B' 与 P[1] 'A' 就失配)
11.    ↓ 再次增加 i ...
13. i=4: T[4...9] vs P[1...6]
14. T: A B C A B C A B D
15. P:     A B C A B D    (匹配成功！ 起始位置为 4)

复制代码

这种方法在大多数情况下表现尚可，期望时间复杂度为 \(O(n+m)\)。但它有一个致命的弱点：在某些特定情况下，其性能会急剧恶化到 \(O(n \times m)\)。
考虑这个“恶意”的例子：

• 文本串 T: AAAAAAAAAAAAAAAAAB
  
• 模式串 P: AAAAAB
  

每次匹配，我们都会在模式串的最后一位 B 才发现失配。而每一次失配，我们都愚蠢地将 i 仅仅增加 1，然后几乎把之前所有成功匹配过的字符又重新比较一遍。
这种大量的重复劳动，是朴素算法效率低下的根源。KMP 算法的革命性思想，正是要彻底消除这种“愚蠢的重复劳动”。
KMP 的跳转思想

KMP 算法的命名来自于它的三位创造者：Knuth、Morris 和 Pratt。它的精髓在于：当发生失配时，我们不把文本串的比较指针 i 回溯，而是根据已经匹配过的内容，将模式串的指针 j “智能地”向前跳转。
我们已经获得的信息是宝贵的财富。当失配发生时，意味着在失配点之前的文本串和模式串部分是完全匹配的。KMP 算法正是要利用这部分已知信息。
案例一：简单的跳转

• 文本串 T: ABCACABABCAB
  
• 模式串 P: ABCAB
  

1. T: A B C A C A B A B C A B
2. P: A B C A B
3.          ↑ (在第5位, T中的'C' 与 P中的'B' 失配)

复制代码

此时，我们已经成功匹配了 ABCA。朴素算法会回溯，从文本串的第 2 位 B 开始重新比较。
KMP 的思考方式是：在已匹配的 ABCA (即 P[1...4]) 中，有没有一个真前缀，和它的真后缀是相同的？
我们发现，前缀 P[1] (A) 和后缀 P[4] (A) 是相同的。这意味着，我们可以保留文本串中已经匹配上的后缀 A，直接将模式串的第 1 位 A 对准它。

1. T: A B C A C A B A B C A B
2. P: A B C A B          (失配前)
4.    ↓ KMP的智能跳转
6. T: A B C A C A B A B C A B
7. P:       A B C A B    (模式串的第1位'A'对准了文本串中刚刚匹配过的'A')

复制代码

我们跳过了两次无效的比较，直接从一个可能成功的位置继续。
案例二：更长的重复

• 文本串 T: ABCABDABABCABC
  
• 模式串 P: ABCABC
  

1. T: A B C A B D A B A B C A B C
2. P: A B C A B C
3.              ↑ (在第6位, T中的'D' 与 P中的'C' 失配)

复制代码

失配前，我们成功匹配了 ABCAB (即 P[1...5])。我们来分析 P[1...5] 的真前缀和真后缀。

• 真前缀：A, AB, ABC, ABCA
  
• 真后缀：B, AB, CAB, BCAB
  

我们发现，最长的一对相同的真前缀和真后缀是 AB。这意味着，文本串中刚刚匹配过的最后两个字符 AB，和模式串的开头两个字符 AB (即 P[1...2]) 是相同的。
KMP 算法告诉我们：太好了！我们不需要从头开始，可以直接将模式串的指针滑到第 3 位，用 P[3] (C) 去和失配的文本串字符 D 继续比较。

1. T: A B C A B D A B A B C A B C
2. P: A B C A B C          (失配前)
4.    ↓ KMP的智能跳转
6. T: A B C A B D A B A B C A B C
7. P:       A B C A B C    (模式串的指针 j 跳转，用 P[3] 对准文本串的'D'继续比较)

复制代码

现在 KMP 的思想已经清晰了：利用失配前已经匹配成功的部分，找到其“最长相等的真前缀和真后缀”，这个前缀的长度就是我们下一次开始比较的位置，从而实现模式串指针的快速跳转。
next 数组的构建

为了实现上述的“智能跳转”，我们需要为模式串预先计算一张“跳转表”，即为本文的 next 数组。next 的核心含义是：在模式串 P 的前缀子串 P[1...i] 中，“最长相等的真前缀和真后缀”的长度。

• 真前缀 (Proper Prefix)：指不包含最后一个字符的所有头部子串。例如 ABCAB 的真前缀有 A, AB, ABC, ABCA。
  
• 真后缀 (Proper Suffix)：指不包含第一个字符的所有尾部子串。例如 ABCAB 的真后缀有 B, AB, CAB, BCAB。
  

示例：构建模式串 P = "abcabc" 的 next 数组
i子串 P[1...i]真前缀真后缀最长相等前后缀next1a(空)(空)(空)02abab(空)03abca, abc, bc(空)04abcaa, ab, abca, ca, bcaa15abcaba, ab, abc, abcab, ab, cab, bcabab26abcabca, ab, abc, abca, abcabc, bc, abc, cabc, bcabcabc3所以，模式串 abcabc 对应的 next 数组为 [0, 0, 0, 1, 2, 3] (这里我们展示了 next[1] 到 next[6] 的值)。
如何高效地计算 next 数组？我们可以用模式串自己和自己匹配的方式来计算。这个过程非常精妙，本身就是一个“小 KMP”。
我们使用两个指针：i 和 j。

• i 是主指针，从 2 开始遍历模式串，代表当前正在计算 next。
  
• j 是辅助指针，初始值为 0。它代表当前已匹配的公共前后缀的长度，同时也指向这个前缀的末尾字符。
  

构建 P = "abacaba" 的 next 数组为例 (m=7)，next 数组初始化为 [0, 0, 0, 0, 0, 0, 0]。

• i = 2: P (b) 与 P[j+1] (P[1], a) 比较。不相等。j 已经是 0，无法回退。next[2] = 0。
  
• i = 3: P (a) 与 P[j+1] (P[1], a) 比较。相等！j 自增为 1。next[3] = j = 1。
  
• i = 4: P (c) 与 P[j+1] (P[2], b) 比较。不相等。j 需要回退。j = next[j] = next[1] = 0。现在 P (c) 和 P[j+1] (P[1], a) 仍不相等。j 无法再回退。next[4] = 0。
  
• i = 5: P (a) 与 P[j+1] (P[1], a) 比较。相等！j 自增为 1。next[5] = j = 1。
  
• i = 6: P (b) 与 P[j+1] (P[2], b) 比较。相等！j 自增为 2。next[6] = j = 2。
  
• i = 7: P (a) 与 P[j+1] (P[3], a) 比较。相等！j 自增为 3。next[7] = j = 3。
  

最终 abacaba 的 next 数组为 [0, 0, 1, 0, 1, 2, 3] (即 next[1] 到 next[7] 的值)。
这个过程的核心在于 j 的回退：当 P ！= P[j+1] 时，我们不是将 j 直接置零，而是令 j = next[j]。这相当于在已经找到的长度为 j 的公共前后缀内部，再寻找一个更短的、长度为 next[j] 的公共前后缀，用它的下一个字符去和 P 尝试匹配。
KMP 匹配全流程

有了 next 数组这张“传送图”，匹配过程就变得非常清晰了。
我们用两个指针：

• i：扫描文本串 T，从 1 到 n，永不回退。
  
• j：扫描模式串 P，初始为 0，代表已匹配的模式串前缀长度。会根据 next 数组进行跳转。
  

示例：

• 文本串 T: ababcabacaba
  
• 模式串 P: abacaba (其 next 数组为 [0, 0, 1, 0, 1, 2, 3])
  

• i=1, j=0: T[1]=='a', P[j+1]=='a'. 匹配. i++, j++. (j=1)
  
• i=2, j=1: T[2]=='b', P[j+1]=='b'. 匹配. i++, j++. (j=2)
  
• i=3, j=2: T[3]=='a', P[j+1]=='a'. 匹配. i++, j++. (j=3)
  
• i=4, j=3: T[4]=='b', P[j+1]=='c'. 失配！
  
  
  
  • 此时 j=3。查询 next 数组：j = next[j] = next[3] = 1。
    
  • 模式串指针 j 跳转，代表当前有长度为 1 的前缀是匹配的。i 保持不变。
    
  • 继续比较 T[4] 和 P[j+1] (即 P[2])。
    
  
  
• i=4, j=1: T[4]=='b', P[j+1]=='b'. 匹配. i++, j++. (j=2)
  
• i=5, j=2: T[5]=='c', P[j+1]=='a'. 失配！
  
  
  
  • 此时 j=2。查询 next 数组：j = next[j] = next[2] = 0。
    
  • 模式串指针 j 跳转到 0。i 保持不变。
    
  
  
• i=5, j=0: T[5]=='c', P[j+1]=='a'. 失配！
  
  
  
  • 此时 j=0，无法再跳转。说明 T[5] 这个字符无法与模式串的第1位匹配。
    
  • i 指针前进一位。i++.
    
  
  
• i=6, j=0: T[6]=='a', P[j+1]=='a'. 匹配. i++, j++. (j=1)
  
• ……（继续匹配）……
  
• i=12, j=6: T[12]=='a', P[j+1]=='a'. 匹配. i++, j++. (j=7)
  

现在 j=7，等于模式串的长度 m。这意味着我们找到了一个完整的匹配！
记录下起始位置：i - m = 13 - 7 = 6。(注意此时 i 已经自增到 13)
或者用失配前的 i 计算：(i-1) - m + 1 = 12 - 7 + 1 = 6。
找到一个匹配后，如何继续寻找下一个？

• 同样利用 next 数组，假装在模式串末尾发生了一次失配：j = next[j] = next[7] = 3。
  
• 从 j=3 的状态开始，与文本串的下一位继续比较，寻找下一个可能的匹配。
  

整个过程中，文本串的指针 i 始终勇往直前，从不后退，这是 KMP 算法效率的根本保证。其总时间复杂度为 \(O(n+m)\)，并且是稳定的，不会退化。
代码实现与解析

1. import sys
3. # 从标准输入读取两行，分别作为文本串和模式串
4. data = sys.stdin.read().split()
5. # 在字符串前加上一个占位符，将索引从 0-based 转换为 1-based
6. # 这样 text_str[i] 就是第 i 个字符，与算法描述一致
7. text_str, pattern_str = '\0' + data[0], '\0' + data[1]
8. text_len, pattern_len = len(text_str) - 1, len(pattern_str) - 1
10. # --- 1. 构建 next 数组 ---
11. # next_arr[i] 存储的是模式串 P[1...i] 的最长相等真前后缀的长度
12. next_arr = [0] * (pattern_len + 1)
13. j = 0 # j 代表当前已匹配的公共前后缀的长度
15. # i 从 2 开始遍历，计算 next_arr[2], next_arr[3], ...
16. for i in range(2, pattern_len + 1):
17.     # 核心跳转逻辑：如果 P[i] 与 P[j+1] 不匹配，
18.     # j 就利用已计算出的 next 值向前回溯，寻找更短的公共前后缀
19.     while j > 0 and pattern_str[i] ！= pattern_str[j + 1]:
20.         j = next_arr[j]
21.    
22.     # 如果 P[i] 与 P[j+1] 匹配成功，公共前后缀长度 j 增加 1
23.     if pattern_str[j + 1] == pattern_str[i]:
24.         j += 1
25.    
26.     # 将计算出的最长公共前后缀长度存入 next_arr[i]
27.     next_arr[i] = j
29. # --- 2. KMP 匹配过程 ---
30. j = 0 # j 是已匹配的模式串前缀长度
31. ans = []  # ans 存储匹配成功的起始位置
32. # i 遍历文本串，从第 1 位到最后一位
33. for i in range(1, text_len + 1):
34.     # 同样的核心跳转逻辑：当文本串字符 T[i] 和模式串字符 P[j+1] 不匹配时，
35.     # 模式串指针 j 根据 next 数组回溯，而文本串指针 i 保持不变
36.     while j > 0 and pattern_str[j + 1] ！= text_str[i]:
37.         j = next_arr[j]
39.     # 如果字符匹配，已匹配长度 j 增加 1
40.     if pattern_str[j + 1] == text_str[i]:
41.         j += 1
43.     # 当 j 等于模式串长度时，说明找到了一个完整的匹配
44.     if j == pattern_len:
45.         # 记录匹配的起始位置 (i - pattern_len + 1)
46.         ans.append(str(i - pattern_len + 1))
47.         # 匹配成功后，继续寻找下一个匹配
48.         # 这步等同于假装在模式串末尾发生了一次失配，j 跳转到相应位置
49.         j = next_arr[j]
51. # --- 结果输出 ---
52. # 按要求格式输出结果
53. output_lines = []
54. if ans:
55.     # 输出所有匹配的起始位置
56.     output_lines.append("\n".join(ans))
57. # 输出计算出的 next 数组 (从第 1 位到最后一位)
58. output_lines.append(" ".join(str(x) for x in next_arr[1:]))
59. sys.stdout.write("\n".join(output_lines))

复制代码

代码逻辑总结：

• 构建 next 数组：for 循环中的 while 循环是 KMP 算法的精华。它实现了在模式串内部的自我匹配和高效回溯，用 \(O(m)\) 的时间复杂度完成了预计算。
  
• 匹配过程：主 for 循环中的 while 循环逻辑与构建 next 数组时高度相似。它保证了文本串指针 i 永不后退，从而实现了 \(O(n)\) 的匹配效率。
  
• 匹配成功后的处理：当 j == pattern_len 时，不仅要记录答案，还要让 j 回溯 (j = next_arr[j])，以便在当前位置之后继续寻找新的匹配，而不是完全重置。
  

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除