KMP算法

学习笔记
,
1.6k words , 6 mins.

什么是 KMP 算法

KMP 算法是一种用于字符串模式匹配的高效算法，由 Knuth、Morris、Pratt 三位大佬于 1977 年提出，算法名称来源于这几个人的名字首字母。可以将时间复杂度从傻瓜式的暴力匹配的 O(m x n) 降低到 O(m + n) 级别，效率提升非常大。

暴力匹配

傻瓜式的暴力匹配原理很简单，对于 text 的第 i 个字符，分别用 p、t 指针分别指向 text 的第 i 个字符、pattern 的起始字符，然后判断两个下标指针位置的字符是否相等；如果相等，则两个下标指针后移一位；如果不相等，则对 text 字符串的第 （i + 1) 个字符循环上述过程，直到 pattern 中的字符全部匹配成功或者到达 text 的最后一个字符。

第一轮：

第二轮：

第三轮：

代码实现如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def match(text, pattern):
    text_list = list(text)
    pattern_list = list(pattern)
    i = 0
    while i < len(text_list):
        t = i
        p = 0
        while t < len(pattern_list):
            if (text_list[t] == pattern_list[p]):
                t += 1
                p += 1
            else:
                break
        
        if p == len(pattern_list):
            return i
        elif t == len(text_list):
            return -1

        i += 1

    return -1

这种匹配方式实现起来非常简单，时间复杂度为 O(m x n)。 但是这样的匹配方式存在回溯问题，每次遇到不匹配的字符时需要回退到 text 的第 i + 1 个字符。

KMP 算法的匹配过程

KMP 算法消除了暴力匹配的回溯问题。

观察匹配过程：

直到第 5 个字符： A、C 不匹配时，前面的 4 个字符都是匹配的，并且观察可以发现前 4 个字符中存在重复的序列 AB，因为前 4 个字符是匹配的，所有同样重复的序列在 pattern 中同样存在。于是可以想有没有可能不回溯 text，而是将 pattern 向右移动，移动时跳过重复的 AB 字符？如下图，这样就能保证在当前匹配到的第 5 个位置之前的字符都是匹配的，然后就可以继续往后匹配了，从而节省回溯 text 之后的几次重复无用匹配。

这就是 KMP 算法的思想，利用 pattern 中子串重复的信息来指示当遇到不匹配字符时 pattern 串应该跳过多少次匹配（也就是跳过多少个存在重复的最长子串），确保 text 不回溯，从而提高匹配的效率。

next 数组就是用来保存 pattern 串中截止到每个字符最长的重复子串信息的。

next 数组

上面提到，next 数组是用来保存 pattern 串中截止到当前字符最长重复子串长度信息的。

要计算 next 数组，需要几个概念：最长前缀、最长后缀和最长公共前后缀。

最长前缀

前缀是指所有以第二个字符开始的连续子串，最长前缀就是这些连续子串中最长的一个。

比如 ABAB ，前缀有：A、AB、ABA，最长前缀为 ABA。

最长后缀

后缀是指所有以倒数第二个字符结尾的连续子串，最长后缀就是这些连续子串中最长的一个。

比如 ABAB 中，后缀有：A、BA、ABA。

最长公共前后缀

就是字符串对应的最长前缀和最长后缀的交集中长度最长的一个。

比如 ABAB 中，公共前缀和后缀有：A、ABA，最长的公共前后缀就是 ABA。

next 数组

next 数组是指字符串中以第一个字符开始，以每个字符结尾的子串对应的最长公共前缀的长度为元素的数组。

比如 ABABC 中：

A：不存在公共前后缀，所以长度为 0。

B：子串为 AB，不存在公共前后缀，所以长度为 0。

A：子串为 ABA，最长公共前后缀为 B，长度为 1。

B：子串为 ABAB，最长公共前后缀为 BA，长度为 2。

C：字串为 ABABC，不存在公共前后缀，所以长度为 0。

于是得到 ABABC 的 next 数组如下。

代码实现 next 数组的计算

可以使用暴力求解，遍历 pattern 字符串，对于每个字符，向前找出所有的前缀、向后找出所有的后缀，求两个集合的交集，如果交集为空，则返回 0，否则取出交集中最长的子串的长度即为结果。

在网上看到有效率更高的方法，采用动态规划，从左到右来求最长公共前后缀。大致过程如下：

  1. 用 next 数组记录结果，用 i 记录当前字符的下标位置，用 lenth 来记录两个指针已经连续匹配上多少个字符，即 text 中对应字符的 next 值。
  2. 初始化时，next[0] = 0 且 i = 1（即默认第一个字符 next 值为 0，从第 2 个字符开始进行计算），length = 0，lenth 用来记录前一个字符的 next 值，并且可以用作第 2 个指针。
  3. 对于 text 中的每个字符：
    1. 如果 text[i] == text[len]，说明当前字符在前面出现过，于是 length + 1，并且两个指针都往后移动一位，即 i + 1，lenth 已经也加过 1。
    2. 如果 text[i] != text[length]，说明重复序列结束了，即 text[0] 至 text[length - 1] 这个子串和 text[i - length] 至 text[i - 1] 这个字串相同，但是 text[0] 至 text[length] 这个子串和 text[i - length] 至 text[i] 这个子串最后一位不相同，相同序列结束了，让 length 指针退回到重复序列之前，即 lenth = next[length - 1]，再重复上面的步骤，如果 length 退回到了起始位置，说明当前字符对应的最长公共子串为 0。

代码实现如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def next(pattern):
    pattern_list = list(pattern)
    next = []
    next.append(0)
    i = 1
    lenth = 0
    while i < len(pattern_list):
        if pattern_list[i] == pattern_list[lenth]:
            lenth += 1
            next.insert(i, lenth)
            i += 1
        else:
            if lenth == 0:
                next.insert(i, 0)
                i += 1
            else:
                lenth = next[lenth - 1]
    return next

代码实现 KMP 算法

求出 next 数组之后，text 中的指针只管往后走，每当遇到不匹配的字符时，只需要将 pattern 中的 p 指针移动到 p - next[p - 1] 的位置处，跳过 next[p - 1] 次比较即可。循环上面的过程，如果 p 指针走到了最后，说明匹配到结果；如果 i 指针走到了最后并且 p 指针没走到最后，则匹配失败。

Python 代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def kmp_match(self, text, pattern):
    next = self.next(pattern)
    text_list = list(text)
    pattern_list = list(pattern)
    i = 0
    p = 0
    while i < len(text_list) and p < len(pattern_list):
        if text_list[i] == pattern_list[p]:
            i += 1
            p += 1
        else:
            p = p - next[p - 1]
    
        if p == len(pattern_list):
            return i - p

    return -1

参考资料

这个算法比较难理解，这次花了很长时间才算是勉强搞明白其中的原理。

可以参考一下这些讲得很不错资料：

B 站上也有一些视频，结合视频动画理解匹配过程会更容易理解。