【kmp算法代码】KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，能够在O(n + m)的时间复杂度内完成模式串与主串的匹配，其中n为主串长度，m为模式串长度。相比传统的暴力匹配算法，KMP通过预处理模式串生成部分匹配表（也称为“失败函数”或“前缀函数”），从而避免了不必要的回溯。
一、KMP算法原理总结
| 概念 | 内容 |
| 目的 | 在主串中查找模式串的出现位置 |
| 时间复杂度 | O(n + m) |
| 核心思想 | 利用已匹配的信息，避免重复比较 |
| 关键步骤 | 预处理生成部分匹配表（next数组） |
二、KMP算法流程
1. 构建next数组：根据模式串计算每个位置的最长前缀和后缀的长度。
2. 匹配过程：使用主串和模式串进行逐个字符比对，当不匹配时，根据next数组调整模式串的位置。
三、KMP算法代码实现（Python）
```python
def kmp_search(text, pattern):
构建next数组
def build_next(pattern):
n = len(pattern)
next_array = [0] n
j = 0
for i in range(1, n):
while j > 0 and pattern[i] != pattern[j]:
j = next_array[j - 1
if pattern[i] == pattern[j]:
j += 1
next_array[i] = j
else:
next_array[i] = 0
return next_array
匹配过程
next_array = build_next(pattern)
j = 0
result = [
for i in range(len(text)):
while j > 0 and text[i] != pattern[j]:
j = next_array[j - 1
if text[i] == pattern[j]:
j += 1
if j == len(pattern):
result.append(i - len(pattern) + 1)
j = next_array[j - 1
return result
```
四、示例说明
假设主串 `text = "ABABABCABAB"`，模式串 `pattern = "ABAB"`，运行上述代码后，输出结果为：
```
| 0, 4, 8 |
```
这表示模式串在主串中分别出现在索引0、4和8的位置。
五、KMP算法优缺点对比
| 特性 | 优点 | 缺点 |
| 时间效率 | 高，线性时间 | 实现较复杂 |
| 空间效率 | 需额外存储next数组 | 一般可接受 |
| 可读性 | 较低 | 需理解next数组逻辑 |
| 应用场景 | 大规模文本匹配 | 小数据量可能不如暴力法快 |
六、总结
KMP算法是字符串匹配中的经典算法，其核心在于利用模式串自身的结构信息来优化匹配过程。虽然实现上略显复杂，但其高效性使其在实际应用中非常受欢迎，尤其是在需要频繁匹配大量文本的场景中。掌握KMP算法不仅有助于提升编程能力，还能加深对字符串处理机制的理解。