写一个完整的KMP算法
时间: 2023-11-18 17:07:32 浏览: 44
KMP算法(Knuth–Morris–Pratt算法)是一种字符串匹配算法,用于在一个文本串S内查找一个模式串P的出现位置。它的核心思想是利用已知信息来避免无效的字符比较,从而达到快速匹配的目的。
以下是KMP算法的完整代码实现:
```python
def kmp(text: str, pattern: str) -> int:
"""
KMP算法实现字符串匹配
:param text: 文本串
:param pattern: 模式串
:return: 如果模式串在文本串中出现,返回第一次出现的位置;否则返回-1
"""
n = len(text)
m = len(pattern)
if m == 0:
return 0
# 构建next数组
next = [-1] * m
j = -1
for i in range(1, m):
while j >= 0 and pattern[j + 1] != pattern[i]:
j = next[j]
if pattern[j + 1] == pattern[i]:
j += 1
next[i] = j
# 匹配文本串和模式串
j = -1
for i in range(n):
while j >= 0 and pattern[j + 1] != text[i]:
j = next[j]
if pattern[j + 1] == text[i]:
j += 1
if j == m - 1:
return i - m + 1
return -1
```
其中,next数组是KMP算法中的一个重要概念。它表示当匹配失败时,模式串应该向右移动的位置。具体地,next[i]表示当模式串中第i个字符与文本串匹配失败时,模式串应该向右移动的位置。如果next[i]的值为j,则表示当匹配失败时,模式串中前j+1个字符和文本串中当前位置之前的j+1个字符是匹配的。在构建next数组时,可以通过一个指针j来记录已经匹配成功的前缀的最后一个字符的下标,并且利用已知信息来推导出下一个字符的匹配位置。具体地,如果pattern[j+1]等于pattern[i],则next[i]的值为j+1;否则,就将j回溯到next[j]的位置,继续匹配。
在匹配文本串和模式串时,也可以利用next数组来避免无效的字符比较。具体地,如果当前字符匹配失败,就将模式串向右移动next[j]个位置,然后再从新的位置开始匹配。这样就可以避免对已经匹配成功的前缀进行重复的比较,提高了匹配的效率。