【kmp算法代码】KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。与传统的暴力匹配算法不同，KMP通过预处理模式串，构建一个部分匹配表（也称为“失败函数”或“前缀函数”），从而在匹配过程中避免重复比较字符，提高效率。
一、KMP算法原理总结
| 项目 | 内容 |
| 算法类型 | 字符串匹配算法 |
| 时间复杂度 | O(n + m)，其中n为文本长度，m为模式串长度 |
| 核心思想 | 利用已匹配部分的信息，避免回溯文本指针 |
| 关键数据结构 | 部分匹配表（next数组） |
| 适用场景 | 多次匹配、大数据量下的高效匹配 |
二、KMP算法流程
1. 预处理阶段：根据模式串生成`next`数组。
2. 匹配阶段：使用`next`数组进行字符匹配，若不匹配则根据`next`调整模式串的位置，而非回退文本指针。
三、KMP算法代码实现（Python）
```python
def kmp_search(text, pattern):
计算next数组
def compute_next(pattern):
m = len(pattern)
next_array = [0] m
j = 0
for i in range(1, m):
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
n = len(text)
m = len(pattern)
if m == 0:
return 0
next_array = compute_next(pattern)
j = 0 模式串指针
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = next_array[j - 1
if text[i] == pattern[j]:
j += 1
if j == m:
print(f"找到匹配，起始位置为 {i - m + 1}")
j = next_array[j - 1
return -1
```
四、示例说明
假设：
- 文本：`"ABABABCABAB"`
- 模式串：`"ABAB"`
运行上述代码后，将输出：
```
找到匹配，起始位置为 0
找到匹配，起始位置为 8
```
五、KMP算法优缺点对比
| 优点 | 缺点 |
| 时间复杂度低，适合大规模数据 | 实现相对复杂，需要理解next数组构造逻辑 |
| 不回溯文本指针，提升效率 | 对于小规模数据，可能不如暴力法快 |
| 适用于多模式匹配场景 | 需要额外空间存储next数组 |
六、总结
KMP算法通过预处理模式串，构建next数组，从而在匹配过程中减少不必要的比较，提升了字符串匹配的效率。它在实际应用中广泛用于文本编辑器、搜索引擎等需要高效字符串查找的场景。虽然实现略复杂，但其性能优势明显，是字符串匹配算法中的经典之作。
