【kmp算法代码】KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在文本中查找模式串的出现位置。与传统的暴力匹配算法不同，KMP通过预处理模式串，构建部分匹配表（也称为“失败函数”或“前缀函数”），从而避免了重复比较，提高了匹配效率。
一、KMP算法原理总结
| 项目 | 内容 |
| 算法类型 | 字符串匹配算法 |
| 时间复杂度 | O(n + m)，其中n为文本长度，m为模式串长度 |
| 空间复杂度 | O(m)（用于存储部分匹配表） |
| 核心思想 | 利用已匹配的部分信息，跳过不必要的字符比较 |
| 预处理阶段 | 构建部分匹配表（prefix function） |
| 匹配阶段 | 使用部分匹配表进行高效匹配 |
二、KMP算法步骤说明
1. 构建部分匹配表（prefix function）
- 对于模式串 `pattern`，计算每个位置的最长前缀和后缀相等的长度。
- 例如：`pattern = "ababc"`，对应的prefix数组为 `[0, 0, 0, 1, 0]`。
2. 匹配过程
- 使用两个指针 `i`（指向文本）和 `j`（指向模式串）。
- 如果字符匹配，则同时移动两个指针；否则，根据prefix表回退 `j` 的位置，继续匹配。
三、KMP算法代码示例（Python）
```python
def kmp_search(text, pattern):
构建部分匹配表
def build_prefix(pattern):
m = len(pattern)
prefix = [0] m
length = 0 前缀和后缀的长度
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
prefix[i] = length
i += 1
else:
if length != 0:
length = prefix[length - 1
else:
prefix[i] = 0
i += 1
return prefix
匹配过程
n = len(text)
m = len(pattern)
if m == 0:
return [
prefix = build_prefix(pattern)
i = j = 0
result = [
while i < n:
if text[i] == pattern[j]:
i += 1
j += 1
if j == m:
result.append(i - j)
j = prefix[j - 1
else:
if j != 0:
j = prefix[j - 1
else:
i += 1
return result
```
四、使用示例
```python
text = "ABABABCABABABC"
pattern = "ABABC"
print(kmp_search(text, pattern)) 输出: [4, 9
```
五、KMP算法优缺点对比
| 特性 | KMP算法 | 暴力算法 |
| 时间复杂度 | O(n + m) | O(nm) |
| 是否避免重复比较 | 是 | 否 |
| 实现难度 | 中等 | 简单 |
| 适用场景 | 大规模文本匹配 | 小规模或简单匹配 |
| 内存占用 | 较高（需存储prefix表） | 低 |
六、总结
KMP算法通过预处理模式串，构建部分匹配表，使得在匹配过程中可以快速回退，避免重复比较，显著提升了字符串匹配的效率。尽管实现略复杂于暴力算法，但在大规模数据处理中具有明显优势。对于需要频繁进行字符串匹配的应用场景，KMP是一个非常实用的算法选择。
