KMP 模式串匹配算法讲解
什么是模式串匹配想象一下，你正在浩如烟海的文本海洋中寻找一根特定的“针”——这就是模式串匹配 (Pattern Matching) 的核心任务。
具体来说，我们有两个字符串：
[*]文本串：一个非常长的字符串，是我们的主要处理对象。例如，一篇数万字的论文、一段基因序列、或者服务器上滚动的日志文件。我们将其记为 T，其长度为 n，字符从 T 到 T。
[*]模式串：一个相对较短的字符串，是我们希望在文本串中寻找的目标。例如，一个特定的关键词、一个已知的病毒基因片段、或者一条特定的错误代码。我们将其记为 P，其长度为 m，字符从 P 到 P。
模式串匹配的目标就是，高效地回答以下问题：
[*]存在性：模式串 P 是否在文本串 T 中出现过？
[*]计数：如果出现过，一共出现了多少次？
[*]定位：每次出现的起始位置在哪里？
这个技术应用极其广泛，举个现实的例子：作为一名社区管理员，你需要处理用户发布的帖子。模式串匹配可以帮助你：
[*]自动审核：快速扫描帖子，查找是否包含“脏字”或“违禁词”（模式串）。
[*]量化惩罚：通过统计违禁词的出现次数，来决定对用户的惩罚等级。
[*]内容净化：精确定位到每个违禁词的出现位置，并自动将其替换为“*”，实现内容屏蔽。
在数据量巨大的今天，匹配算法的效率至关重要。一个糟糕的算法可能会让用户等待数秒甚至数分钟，而一个优秀的算法则能在瞬间完成任务。KMP 算法，就是这其中的佼佼者。
朴素匹配算法的瓶颈
在深入 KMP 的精妙之处前，我们先来回顾最直观的匹配方法——朴素匹配算法（也称暴力匹配算法）。
它的思路简单粗暴：
[*]从文本串的第 i 个位置开始（i 从 1 到 n-m+1），将模式串 P 与文本串的子串 T 进行逐位比较。
[*]如果所有 m 个字符都匹配成功，就记录下起始位置 i，完成一次查找。
[*]如果在比较过程中，发现某一位字符不匹配（我们称之为“失配”），就立即停止本次比较。
[*]i 增加 1，回到第 1 步，开始新一轮的比较。
让我们看一个例子：
[*]文本串 T: ABCABCABD
[*]模式串 P: ABCABD
i=1: T vs P
T: A B C A B C A B D
P: A B C A B D (在第6位, T 'C' 与 P 'D' 失配)
↓ 失配后，i 增加 1，从 i=2 开始重新比较
i=2: T vs P
T: A B C A B C A B D
P: A B C A B D (在第1位, T 'B' 与 P 'A' 就失配)
↓ 再次增加 i ...
i=4: T vs P
T: A B C A B C A B D
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
T: A B C A C A B A B C A B
P: A B C A B
↑ (在第5位, T中的'C' 与 P中的'B' 失配)此时，我们已经成功匹配了 ABCA。朴素算法会回溯，从文本串的第 2 位 B 开始重新比较。
KMP 的思考方式是：在已匹配的 ABCA (即 P) 中，有没有一个真前缀，和它的真后缀是相同的？
我们发现，前缀 P (A) 和后缀 P (A) 是相同的。这意味着，我们可以保留文本串中已经匹配上的后缀 A，直接将模式串的第 1 位 A 对准它。
T: A B C A C A B A B C A B
P: A B C A B (失配前)
↓ KMP的智能跳转
T: A B C A C A B A B C A B
P: A B C A B (模式串的第1位'A'对准了文本串中刚刚匹配过的'A')我们跳过了两次无效的比较，直接从一个可能成功的位置继续。
案例二：更长的重复
[*]文本串 T: ABCABDABABCABC
[*]模式串 P: ABCABC
T: A B C A B D A B A B C A B C
P: A B C A B C
↑ (在第6位, T中的'D' 与 P中的'C' 失配)失配前，我们成功匹配了 ABCAB (即 P)。我们来分析 P 的真前缀和真后缀。
[*]真前缀：A, AB, ABC, ABCA
[*]真后缀：B, AB, CAB, BCAB
我们发现，最长的一对相同的真前缀和真后缀是 AB。这意味着，文本串中刚刚匹配过的最后两个字符 AB，和模式串的开头两个字符 AB (即 P) 是相同的。
KMP 算法告诉我们：太好了！我们不需要从头开始，可以直接将模式串的指针滑到第 3 位，用 P (C) 去和失配的文本串字符 D 继续比较。
T: A B C A B D A B A B C A B C
P: A B C A B C (失配前)
↓ KMP的智能跳转
T: A B C A B D A B A B C A B C
P: A B C A B C (模式串的指针 j 跳转，用 P 对准文本串的'D'继续比较)现在 KMP 的思想已经清晰了：利用失配前已经匹配成功的部分，找到其“最长相等的真前缀和真后缀”，这个前缀的长度就是我们下一次开始比较的位置，从而实现模式串指针的快速跳转。
next 数组的构建
为了实现上述的“智能跳转”，我们需要为模式串预先计算一张“跳转表”，即为本文的 next 数组。next 的核心含义是：在模式串 P 的前缀子串 P 中，“最长相等的真前缀和真后缀”的长度。
[*]真前缀 (Proper Prefix)：指不包含最后一个字符的所有头部子串。例如 ABCAB 的真前缀有 A, AB, ABC, ABCA。
[*]真后缀 (Proper Suffix)：指不包含第一个字符的所有尾部子串。例如 ABCAB 的真后缀有 B, AB, CAB, BCAB。
示例：构建模式串 P = "abcabc" 的 next 数组
i子串 P真前缀真后缀最长相等前后缀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 数组为 (这里我们展示了 next 到 next 的值)。
如何高效地计算 next 数组？我们可以用模式串自己和自己匹配的方式来计算。这个过程非常精妙，本身就是一个“小 KMP”。
我们使用两个指针：i 和 j。
[*]i 是主指针，从 2 开始遍历模式串，代表当前正在计算 next。
[*]j 是辅助指针，初始值为 0。它代表当前已匹配的公共前后缀的长度，同时也指向这个前缀的末尾字符。
构建 P = "abacaba" 的 next 数组为例 (m=7)，next 数组初始化为 。
[*]i = 2: P (b) 与 P (P, a) 比较。不相等。j 已经是 0，无法回退。next = 0。
[*]i = 3: P (a) 与 P (P, a) 比较。相等！j 自增为 1。next = j = 1。
[*]i = 4: P (c) 与 P (P, b) 比较。不相等。j 需要回退。j = next = next = 0。现在 P (c) 和 P (P, a) 仍不相等。j 无法再回退。next = 0。
[*]i = 5: P (a) 与 P (P, a) 比较。相等！j 自增为 1。next = j = 1。
[*]i = 6: P (b) 与 P (P, b) 比较。相等！j 自增为 2。next = j = 2。
[*]i = 7: P (a) 与 P (P, a) 比较。相等！j 自增为 3。next = j = 3。
最终 abacaba 的 next 数组为 (即 next 到 next 的值)。
这个过程的核心在于 j 的回退：当 P ！= P 时，我们不是将 j 直接置零，而是令 j = next。这相当于在已经找到的长度为 j 的公共前后缀内部，再寻找一个更短的、长度为 next 的公共前后缀，用它的下一个字符去和 P 尝试匹配。
KMP 匹配全流程
有了 next 数组这张“传送图”，匹配过程就变得非常清晰了。
我们用两个指针：
[*]i：扫描文本串 T，从 1 到 n，永不回退。
[*]j：扫描模式串 P，初始为 0，代表已匹配的模式串前缀长度。会根据 next 数组进行跳转。
示例：
[*]文本串 T: ababcabacaba
[*]模式串 P: abacaba (其 next 数组为 )
[*]i=1, j=0: T=='a', P=='a'. 匹配. i++, j++. (j=1)
[*]i=2, j=1: T=='b', P=='b'. 匹配. i++, j++. (j=2)
[*]i=3, j=2: T=='a', P=='a'. 匹配. i++, j++. (j=3)
[*]i=4, j=3: T=='b', P=='c'. 失配！
[*]此时 j=3。查询 next 数组：j = next = next = 1。
[*]模式串指针 j 跳转，代表当前有长度为 1 的前缀是匹配的。i 保持不变。
[*]继续比较 T 和 P (即 P)。
[*]i=4, j=1: T=='b', P=='b'. 匹配. i++, j++. (j=2)
[*]i=5, j=2: T=='c', P=='a'. 失配！
[*]此时 j=2。查询 next 数组：j = next = next = 0。
[*]模式串指针 j 跳转到 0。i 保持不变。
[*]i=5, j=0: T=='c', P=='a'. 失配！
[*]此时 j=0，无法再跳转。说明 T 这个字符无法与模式串的第1位匹配。
[*]i 指针前进一位。i++.
[*]i=6, j=0: T=='a', P=='a'. 匹配. i++, j++. (j=1)
[*]……（继续匹配）……
[*]i=12, j=6: T=='a', P=='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 = next = 3。
[*]从 j=3 的状态开始，与文本串的下一位继续比较，寻找下一个可能的匹配。
整个过程中，文本串的指针 i 始终勇往直前，从不后退，这是 KMP 算法效率的根本保证。其总时间复杂度为 \(O(n+m)\)，并且是稳定的，不会退化。
代码实现与解析
import sys
# 从标准输入读取两行，分别作为文本串和模式串
data = sys.stdin.read().split()
# 在字符串前加上一个占位符，将索引从 0-based 转换为 1-based
# 这样 text_str 就是第 i 个字符，与算法描述一致
text_str, pattern_str = '\0' + data, '\0' + data
text_len, pattern_len = len(text_str) - 1, len(pattern_str) - 1
# --- 1. 构建 next 数组 ---
# next_arr 存储的是模式串 P 的最长相等真前后缀的长度
next_arr = * (pattern_len + 1)
j = 0 # j 代表当前已匹配的公共前后缀的长度
# i 从 2 开始遍历，计算 next_arr, next_arr, ...
for i in range(2, pattern_len + 1):
# 核心跳转逻辑：如果 P 与 P 不匹配，
# j 就利用已计算出的 next 值向前回溯，寻找更短的公共前后缀
while j > 0 and pattern_str ！= pattern_str:
j = next_arr
# 如果 P 与 P 匹配成功，公共前后缀长度 j 增加 1
if pattern_str == pattern_str:
j += 1
# 将计算出的最长公共前后缀长度存入 next_arr
next_arr = j
# --- 2. KMP 匹配过程 ---
j = 0 # j 是已匹配的模式串前缀长度
ans = []# ans 存储匹配成功的起始位置
# i 遍历文本串，从第 1 位到最后一位
for i in range(1, text_len + 1):
# 同样的核心跳转逻辑：当文本串字符 T 和模式串字符 P 不匹配时，
# 模式串指针 j 根据 next 数组回溯，而文本串指针 i 保持不变
while j > 0 and pattern_str ！= text_str:
j = next_arr
# 如果字符匹配，已匹配长度 j 增加 1
if pattern_str == text_str:
j += 1
# 当 j 等于模式串长度时，说明找到了一个完整的匹配
if j == pattern_len:
# 记录匹配的起始位置 (i - pattern_len + 1)
ans.append(str(i - pattern_len + 1))
# 匹配成功后，继续寻找下一个匹配
# 这步等同于假装在模式串末尾发生了一次失配，j 跳转到相应位置
j = next_arr
# --- 结果输出 ---
# 按要求格式输出结果
output_lines = []
if ans:
# 输出所有匹配的起始位置
output_lines.append("\n".join(ans))
# 输出计算出的 next 数组 (从第 1 位到最后一位)
output_lines.append(" ".join(str(x) for x in next_arr))
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)，以便在当前位置之后继续寻找新的匹配，而不是完全重置。
来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除
页:
[1]