张芷铭的个人博客

#算法 #字符串匹配 #KMP

KMP 算法利用已匹配信息避免从头搜索，时间复杂度 O(n+m)，远优于暴力搜索的 O(n×m)。

核心思想

当发生不匹配时，利用部分匹配表（next 数组） 决定模式串移动距离，而非重新开始比较。

next 数组构建

next[i] 表示 P[0..i] 的最长相同前后缀长度：

1
2

P:  A  B  C  D  A  B  D
   0  0  0  0  1  2  0

完整实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def KMP_search(T, P):
    def build_next(P):
        table = [0] * len(P)
        length = 0
        i = 1
        while i < len(P):
            if P[i] == P[length]:
                length += 1
                table[i] = length
                i += 1
            elif length != 0:
                length = table[length - 1]
            else:
                table[i] = 0
                i += 1
        return table

    next_arr = build_next(P)
    i = j = 0
    while i < len(T):
        if P[j] == T[i]:
            i += 1
            j += 1
        elif j > 0:
            j = next_arr[j - 1]
        else:
            i += 1

        if j == len(P):
            print(f"Found at index {i - j}")
            j = next_arr[j - 1]

复杂度分析

  • 时间复杂度：O(n + m)，n 为文本长度，m 为模式长度
  • 空间复杂度：O(m)，存储 next 数组

学习资源

最浅显易懂的 KMP 算法讲解

Comments