kmp算法代码

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。与传统的暴力匹配算法不同，KMP通过预处理模式串，构建一个部分匹配表（也称为“失败函数”或“前缀函数”），从而在匹配过程中避免重复比较字符，提高效率。

一、KMP算法原理总结

二、KMP算法流程

1. 预处理阶段：根据模式串生成`next`数组。

2. 匹配阶段：使用`next`数组进行字符匹配，若不匹配则根据`next`调整模式串的位置，而非回退文本指针。

三、KMP算法代码实现（Python）

```python

def kmp_search(text, pattern):

计算next数组

def compute_next(pattern):

m = len(pattern)

next_array = [0] m

j = 0

for i in range(1, m):

while j > 0 and pattern[i] != pattern[j]:

j = next_array[j - 1

if pattern[i] == pattern[j]:

j += 1

next_array[i] = j

else:

next_array[i] = 0

return next_array

n = len(text)

m = len(pattern)

if m == 0:

return 0

next_array = compute_next(pattern)

j = 0 模式串指针

for i in range(n):

while j > 0 and text[i] != pattern[j]:

j = next_array[j - 1

if text[i] == pattern[j]:

j += 1

if j == m:

print(f"找到匹配，起始位置为 {i - m + 1}")

j = next_array[j - 1

return -1

```

四、示例说明

假设：

- 文本：`"ABABABCABAB"`

- 模式串：`"ABAB"`

运行上述代码后，将输出：

```

找到匹配，起始位置为 0

找到匹配，起始位置为 8

```

五、KMP算法优缺点对比

六、总结

KMP算法通过预处理模式串，构建next数组，从而在匹配过程中减少不必要的比较，提升了字符串匹配的效率。它在实际应用中广泛用于文本编辑器、搜索引擎等需要高效字符串查找的场景。虽然实现略复杂，但其性能优势明显，是字符串匹配算法中的经典之作。