实现KMP算法,给出Python代码
时间: 2024-03-28 17:11:28 浏览: 19
好的,我可以帮您给出 Python 实现 KMP 算法的代码,以下是示例代码:
```python
def kmp(text, pattern):
n, m = len(text), len(pattern)
if m == 0:
return 0
# 构建 next 数组
next = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = next[j - 1]
if pattern[i] == pattern[j]:
j += 1
next[i] = j
# 匹配过程
j = 0
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = next[j - 1]
if text[i] == pattern[j]:
j += 1
if j == m:
return i - m + 1
return -1
```
调用 kmp 函数即可实现在文本中查找模式字符串的功能,例如:
```python
text = "ABCABCDABCDABDE"
pattern = "ABCDABD"
print(kmp(text, pattern)) # 输出 6
```
注意,上述代码并不一定是最优的实现,其中有很多可以优化的地方。如果需要更高效的实现,您可以参考其他资源。