KMP算法的完整代码
时间: 2024-09-19 12:13:05 浏览: 32
KMP(Knuth-Pratt)算法是一种高效的字符串匹配算法,用于在一个较长的文本串(主串)中查找一个较短的模式串。它利用了前缀函数(也叫部分匹配表)来避免无效的匹配尝试,减少了回溯次数。
以下是KMP算法的Python实现:
```python
def build_prefix_table(pattern):
prefix = [0] * len(pattern)
j = -1
for i in range(1, len(pattern)):
while j != -1 and pattern[i] != pattern[j + 1]:
j = prefix[j]
if pattern[i] == pattern[j + 1]:
j += 1
prefix[i] = j
return prefix
def kmp_search(text, pattern):
text_len = len(text)
pattern_len = len(pattern)
prefix_table = build_prefix_table(pattern)
j = 0
for i in range(text_len):
if text[i] == pattern[j]:
if j == pattern_len - 1:
return i - pattern_len + 1 # 找到匹配位置
j += 1
elif j > 0:
j = prefix_table[j - 1]
else:
continue
return -1 # 没有找到匹配
# 使用示例
text = "ABABDABACDABABC"
pattern = "ABCD"
match_index = kmp_search(text, pattern)
if match_index != -1:
print(f"Pattern found at index {match_index}")
else:
print("Pattern not found")
```
在这个代码中,`build_prefix_table`函数计算前缀函数,`kmp_search`函数根据前缀函数进行匹配搜索。如果找到了匹配,就返回该位置;如果没有找到,则返回-1。