编写一个kmp算法的代码
时间: 2024-05-02 15:21:03 浏览: 15
以下是一个基本的KMP算法的代码实现:
```python
def kmp(text, pattern):
n, m = len(text), len(pattern)
if m == 0:
return 0
if n == 0:
return -1
lps = compute_lps(pattern)
i, j = 0, 0
while i < n:
if text[i] == pattern[j]:
i += 1
j += 1
if j == m:
return i - j
elif j > 0:
j = lps[j-1]
else:
i += 1
return -1
def compute_lps(pattern):
lps = [0] * len(pattern)
j = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[j]:
j += 1
lps[i] = j
i += 1
elif j > 0:
j = lps[j-1]
else:
lps[i] = 0
i += 1
return lps
```
在这个实现中,`kmp`函数接受两个字符串,`text`和`pattern`,并返回`pattern`在`text`中第一次出现的索引位置。如果`pattern`未在`text`中找到,则返回`-1`。实现中使用了`compute_lps`函数来计算`pattern`的最长前缀后缀(Longest Prefix Suffix,LPS)数组。在`kmp`函数的主体中,我们使用两个指针`i`和`j`来遍历`text`和`pattern`。如果`text[i]`和`pattern[j]`相等,我们将两个指针都向前移动一步。如果`j`等于`m`,说明我们已经在`text`中找到了一个与`pattern`匹配的子串,返回`i - j`即为该子串的起始位置。如果`text[i]`和`pattern[j]`不相等,则我们将`j`移回LPS数组的上一个元素,如果`j`已经为0,我们只将`i`向前移动一步。
这个实现中的时间复杂度为$O(n+m)$,其中$n$为`text`的长度,$m$为`pattern`的长度。LPS数组的计算需要$O(m)$的时间,而KMP算法的主体需要$O(n)$的时间。