实现字符串匹配KMP算法
时间: 2023-11-18 09:53:12 浏览: 42
KMP算法是一种字符串匹配算法,它的核心思想是利用已知信息来避免无效的比较。具体来说,KMP算法通过预处理模式串,得到一个next数组,用于指导匹配过程中的跳转操作。下面是KMP算法的实现代码:
```python
def kmp(text, pattern):
n, m = len(text), len(pattern)
if m == 0:
return 0
next = get_next(pattern)
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
def get_next(pattern):
m = len(pattern)
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
return next
```
其中,get_next函数用于计算next数组,kmp函数用于进行匹配。具体实现过程可以参考注释。