KMP算法
KMP算法[编辑 | 编辑源代码]
KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，用于在主文本字符串中查找模式字符串的出现位置。该算法通过利用模式字符串的部分匹配信息来避免不必要的字符比较，从而将时间复杂度从朴素算法的O(m*n)优化到O(m+n)，其中m是模式串的长度，n是主文本的长度。
算法原理[编辑 | 编辑源代码]
KMP算法的核心思想是当模式串与主文本不匹配时，利用已知的匹配信息跳过一些不可能成功的比较。具体来说，它通过预处理模式串生成一个部分匹配表（Partial Match Table，简称PMT），也称为失败函数（Failure Function），来指导匹配失败时的跳转。
部分匹配表（PMT）[编辑 | 编辑源代码]
部分匹配表记录了模式串中每个位置的最长公共前后缀长度。例如，对于模式串"ABABC"：
| 索引 | 子串 | 最长公共前后缀长度 |
|---|---|---|
| 0 | A | 0 |
| 1 | AB | 0 |
| 2 | ABA | 1 ("A") |
| 3 | ABAB | 2 ("AB") |
| 4 | ABABC | 0 |
数学表示为：
算法步骤[编辑 | 编辑源代码]
1. 预处理阶段：构建模式串的部分匹配表。 2. 匹配阶段：使用部分匹配表在主文本中查找模式串。
预处理实现[编辑 | 编辑源代码]
以下是构建部分匹配表的Python实现：
def build_pmt(pattern):
pmt = [0] * len(pattern)
length = 0 # 当前最长公共前后缀长度
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
pmt[i] = length
i += 1
else:
if length != 0:
length = pmt[length - 1]
else:
pmt[i] = 0
i += 1
return pmt
匹配实现[编辑 | 编辑源代码]
使用PMT进行字符串匹配：
def kmp_search(text, pattern):
pmt = build_pmt(pattern)
i = j = 0 # i遍历text，j遍历pattern
while i < len(text):
if text[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
print(f"Pattern found at index {i - j}")
j = pmt[j - 1]
else:
if j != 0:
j = pmt[j - 1]
else:
i += 1
示例分析[编辑 | 编辑源代码]
输入：
- 主文本： "ABABDABACDABABCABAB"
- 模式串： "ABABCABAB"
输出： Pattern found at index 10
匹配过程可视化：
时间复杂度分析[编辑 | 编辑源代码]
- 预处理阶段：O(m)
- 匹配阶段：O(n)
- 总时间复杂度：O(m+n)
对比朴素算法的O(m*n)，KMP在重复模式较多的场景下优势显著。
实际应用[编辑 | 编辑源代码]
KMP算法广泛应用于： 1. 文本编辑器的查找功能 2. DNA序列匹配 3. 网络数据包的内容检测 4. 编译器的词法分析
变体与扩展[编辑 | 编辑源代码]
- Boyer-Moore算法：另一种高效字符串匹配算法，适合字符集较大的情况
- Rabin-Karp算法：基于哈希的字符串匹配算法
- Aho-Corasick算法：多模式串匹配的扩展
练习建议[编辑 | 编辑源代码]
1. 手动计算模式串"AAAAB"的部分匹配表 2. 实现KMP算法并测试不同输入 3. 比较KMP与朴素算法的性能差异 4. 尝试修改算法以查找所有匹配位置