python kmp算法
时间: 2023-09-11 14:04:08 浏览: 52
KMP算法是一种字符串匹配算法,用于查找一个字符串(模式串)在另一个字符串(文本串)中的出现位置。它的时间复杂度为O(m+n),其中m和n分别是模式串和文本串的长度。
KMP算法的核心思想是利用已经匹配过的部分来跳过一些无需匹配的部分,从而提高匹配效率。具体实现如下:
1. 预处理模式串,生成next数组。next[i]表示模式串前i个字符组成的子串中,最长的相等前缀后缀的长度。例如,模式串"ABCDABD"的next数组为[-1,0,0,0,0,1,2,0]。
2. 在文本串中匹配模式串。从文本串的第一个字符开始,依次和模式串进行匹配。如果匹配成功,继续匹配下一个字符;如果匹配失败,则根据next数组跳过一些无需匹配的部分。
代码实现如下:
```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
```
其中,next数组的生成过程采用了类似动态规划的思想,通过已经匹配过的部分来推导下一步的匹配位置。在匹配过程中,如果当前字符匹配失败,则根据next数组跳过一些无需匹配的部分,以提高匹配效率。