【kmp算法代码】KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在主串中查找模式串的出现位置。与传统的暴力匹配方法相比，KMP算法通过预处理模式串，构建部分匹配表（也称为失败函数或前缀函数），从而避免了重复比较字符，提高了匹配效率。
一、KMP算法概述
| 特性 | 描述 |
| 算法类型 | 字符串匹配算法 |
| 时间复杂度 | O(n + m)，其中n为文本长度，m为模式串长度 |
| 空间复杂度 | O(m)（用于存储部分匹配表） |
| 是否需要预处理 | 是（构建部分匹配表） |
| 适用场景 | 高效字符串匹配，尤其适用于大文本和模式串 |
二、KMP算法核心思想
KMP算法的核心是利用模式串自身的前缀和后缀信息，当发生不匹配时，不需要回溯主串指针，而是根据部分匹配表调整模式串的位置，从而减少不必要的比较。
1. 构建部分匹配表（next数组）
对于模式串 `pattern`，计算每个位置的最长公共前后缀长度，形成一个数组 `next`。
2. 进行匹配
使用两个指针 `i`（主串指针）、`j`（模式串指针），逐个比较字符。若匹配成功，则 `j++`；若不匹配，则根据 `next[j-1]` 调整 `j` 的位置，继续比较。
三、KMP算法代码实现（Python）
```python
def kmp_search(text, pattern):
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)
i = j = 0
n = len(text)
m = len(pattern)
result = [
while i < n:
if text[i] == pattern[j]:
i += 1
j += 1
if j == m:
result.append(i - j)
j = next_array[j - 1
else:
if j != 0:
j = next_array[j - 1
else:
i += 1
return result
```
四、示例说明
假设主串 `text = "ABABCABAB"`，模式串 `pattern = "ABAB"`，运行上述代码将返回 `[0, 4]`，表示模式串在主串中的起始位置为0和4。
五、总结
| 项目 | 内容 |
| KMP算法 | 一种高效字符串匹配算法 |
| 关键点 | 部分匹配表（next数组） |
| 优点 | 避免回溯主串，提高效率 |
| 实现步骤 | 构建next数组 → 匹配过程 |
| 应用场景 | 大规模文本搜索、字符串处理等 |
KMP算法因其高效的匹配性能，在实际应用中被广泛使用，特别是在处理大量数据时，能够显著提升程序运行效率。