【kmp算法代码】KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，能够在O(n + m)的时间复杂度内完成模式串与主串的匹配，避免了传统暴力匹配中重复回溯的问题。本文将对KMP算法的核心思想进行总结，并提供相应的代码实现。
一、KMP算法核心思想
KMP算法的关键在于构建一个“部分匹配表”（也称为前缀函数或失败函数），用于在匹配失败时决定模式串应跳转的位置，从而避免重复比较。
1. 前缀函数（Prefix Function）
对于模式串`pattern`，定义一个数组`lps`（Longest Prefix Suffix），其中`lps[i]`表示子串`pattern[0..i]`中最长的前缀和后缀相等的长度（不包括整个子串本身）。
2. 匹配过程
使用两个指针`i`（主串索引）、`j`（模式串索引）。当字符匹配时，同时移动；当不匹配时，根据`lps[j-1]`调整`j`的位置，继续匹配。
二、KMP算法步骤总结
| 步骤 | 描述 |
| 1 | 构建模式串的`lps`数组 |
| 2 | 初始化主串索引`i = 0`，模式串索引`j = 0` |
| 3 | 当`i < len(text)`且`j < len(pattern)`时循环： |
| 4 | 如果`text[i] == pattern[j]`，则`i++`, `j++` |
| 5 | 否则，如果`j != 0`，则`j = lps[j - 1]` |
| 6 | 否则，`i++` |
| 7 | 若`j == len(pattern)`，说明找到匹配位置 |
三、KMP算法代码实现（Python）
```python
def compute_lps(pattern):
lps = [0] len(pattern)
length = 0 长度为当前最长前缀后缀匹配长度
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1
else:
lps[i] = 0
i += 1
return lps
def kmp_search(text, pattern):
n = len(text)
m = len(pattern)
lps = compute_lps(pattern)
i = j = 0
while i < n:
if pattern[j] == text[i]:
i += 1
j += 1
if j == m:
print(f"Pattern found at index {i - j}")
j = lps[j - 1
elif i < n and pattern[j] != text[i]:
if j != 0:
j = lps[j - 1
else:
i += 1
```
四、示例运行
假设主串为 `"ABABABCABABABC"`，模式串为 `"ABABABC"`，运行KMP算法后，将输出：
```
Pattern found at index 0
Pattern found at index 8
```
五、总结
KMP算法通过预处理模式串，构建前缀函数表，避免了不必要的回溯，提升了字符串匹配效率。适用于大规模文本搜索场景，如文本编辑器、搜索引擎等。掌握其原理和实现方式，有助于提高算法设计能力。