kmp算法python
时间: 2023-09-11 20:04:46 浏览: 48
下面是KMP算法的Python代码:
```python
def KMP(text, pattern):
m = len(pattern)
n = len(text)
lps = [0] * m
j = 0
computeLPS(pattern, m, lps)
i = 0
while i < n:
if pattern[j] == text[i]:
i += 1
j += 1
if j == m:
print("Found pattern at index " + str(i-j))
j = lps[j-1]
elif i < n and pattern[j] != text[i]:
if j != 0:
j = lps[j-1]
else:
i += 1
def computeLPS(pattern, m, lps):
len = 0
lps[0] = 0
i = 1
while i < m:
if pattern[i] == pattern[len]:
len += 1
lps[i] = len
i += 1
else:
if len != 0:
len = lps[len-1]
else:
lps[i] = 0
i += 1
```
其中,KMP函数用于在text字符串中搜索pattern字符串。computeLPS函数用于计算pattern字符串的最长前缀和最长后缀匹配数组(lps数组)。KMP算法的主要思想是在匹配过程中,如果发现当前字符不匹配,则利用lps数组跳过已经匹配的部分,从下一个字符开始继续匹配。