【kmp算法代码】KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主串中查找子串的出现位置。与传统的暴力匹配方法不同，KMP通过预处理子串，构建一个部分匹配表（也称为失败函数或前缀函数），从而避免了重复匹配，提高了算法效率。
一、KMP算法核心思想
KMP算法的核心在于利用已经匹配的信息，避免不必要的回溯。当在主串中匹配到不一致字符时，KMP会根据之前匹配的结果调整子串的位置，而不是从头开始匹配。
二、KMP算法步骤
1. 构建前缀数组（部分匹配表）：
对于子串 `pattern`，计算每个位置的最长前缀和后缀的长度，形成一个数组 `lps`。
2. 进行匹配过程：
使用两个指针分别指向主串 `text` 和子串 `pattern`，根据 `lps` 数组调整匹配位置。
三、KMP算法代码实现
以下为Python语言实现的KMP算法代码：
```python
def kmp_search(text, pattern):
n = len(text)
m = len(pattern)
构建lps数组
lps = [0] m
length = 0 当前最长前缀后缀的长度
for i in range(1, m):
while length > 0 and pattern[i] != pattern[length]:
length = lps[length - 1
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
else:
lps[i] = 0
匹配过程
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
```
四、KMP算法对比总结
| 特性 | KMP算法 | 暴力算法 |
| 时间复杂度 | O(n + m) | O(nm) |
| 是否回溯 | 不回溯 | 需要回溯 |
| 预处理 | 需要构建lps数组 | 无需预处理 |
| 空间复杂度 | O(m) | O(1) |
| 适用场景 | 大规模文本匹配 | 小规模文本匹配 |
五、总结
KMP算法通过构建前缀数组，实现了高效的字符串匹配，避免了传统算法中的重复比较。其时间复杂度为线性，适用于大规模数据的匹配任务。虽然空间复杂度略高，但在实际应用中具有较高的性能优势。对于需要频繁进行字符串匹配的应用场景，KMP是一个非常实用的选择。