KMP（Knuth-Morris-Pratt）算法是一种用于字符串搜索的高效算法，其核心思想是当在文本字符串中搜索一个词时，能够利用已经部分匹配的信息避免从头开始搜索，从而提高搜索效率。这是通过预处理模式字符串来实现的，预处理阶段生成一个部分匹配表（也称为前缀表或失败函数），该表被用来决定下一步的搜索位置。

KMP算法的工作原理

假设有文本字符串T和模式字符串P，我们的目标是在T中找到P的出现位置。

预处理阶段：生成模式字符串P的部分匹配表 next数组 。这个表会告诉我们在不匹配发生时，模式字符串P应该如何移动。对于P中的每一个位置i，部分匹配表记录了P[0..i]的前缀与后缀的最长公共元素的长度。这个值也表示当发生不匹配时，P应该向右移动的距离。
搜索阶段：使用部分匹配表来执行搜索。当T和P在某个位置不匹配时，我们可以利用部分匹配表来决定P下一步应该移动多远，而不是简单地将P向右移动一位。这样，我们就可以跳过一些不必要的比较。

优点

KMP算法的主要优势在于其高效性。在最坏情况下，它的时间复杂度是线性的，即O(n+m)，其中n是文本字符串T的长度，m是模式字符串P的长度。这比简单的暴力搜索算法要好得多，后者在最坏情况下的时间复杂度为O(n*m)。

示例

考虑模式字符串P = "ABCDABD"，它的部分匹配表如下：

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

如果在文本字符串T中搜索P，当我们发现第六个字符（假设为B）与T中的某个字符不匹配时，根据部分匹配表，我们可以将P向右移动2位，而不是重新开始比较。

实现

 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
32
33
34
35
36
37
38
def KMP_search(T, P):
    # 部分匹配表的构建
    def build_partial_match_table(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
            else:
                if length != 0:
                    length = table[length - 1]
                else:
                    table[i] = 0
                    i += 1
        return table
    
    table = build_partial_match_table(P)
    i = j = 0
    while i < len(T):
        if P[j] == T[i]:
            i += 1
            j += 1
        elif j > 0: # 字符失配，根据table跳过一些字符
            j = table[j - 1]
        else:
            i += 1 # j==0 的情况，第一个字符就失配
            
        if j == len(P):
            print("Found pattern at index " + str(i - j))
            j = table[j - 1] # 为了找到所有的匹配的index

# 使用示例
T = "ABABDABACDABABCABAB"
P = "ABABCABAB"
KMP_search(T, P)

KMP算法：字符串匹配

KMP算法的工作原理

优点

示例

实现

相关的面试题

💬 评论