24 字符串匹配之 KMP 算法

2018-10-31 约 2009 字预计阅读 5 分钟

优雅的的 KMP 算法

1. KMP 算法

BM（Boyer-Moore）和 KMP(Knuth-Morris-Pratt) 都是非常高效的字符串匹配算法。BM 比 KMP 更高效，有实验统计 BM 的性能是 KMP 3-4 倍。但是他们都非常复杂难懂。除了专栏，我也非常推荐你看一看阮一峰老师有关 BM 和 KMP 算法的介绍。因为 BM 算法利用到了KMP的算法思想，本节我们就先来介绍 KMP 的实现。

1.1 优化思路

KMP 算法基于这样一个实现思路: 如下图所示，对于字符串匹配过程中已经匹配的部分，我们是已知的；利用这个已知的信息，我们可以把模式串往后移动更多位，而不是 BR 算法中的一位。而最终移动的位数取决于已匹配部分的"前缀"和"后缀"的最长的共有元素的长度，我们将这个最长的公共子串称为最长可匹配(前缀/后缀)子串

在上面的图例中，已匹配部分是 ABCDAB，前后缀最长匹配的元素是 AB，因此前缀 AB就可以直接来到后缀AB的位置，直接向后移动 4 位继续匹配，如下图所示。

字符串已匹配部分永远是模式串的前缀子串，因此最长可匹配(前缀/后缀)子串我们可以提前计算出来，这个就是 KMP 中的 部分匹配表。因此，整个 KMP 的计算过程就分成了两步:

计算部分匹配表
根据部分匹配表计算每次不匹配时，模式串的移动位数，进行字符串匹配

1.2 部分匹配表

部分匹配表，被称为失效函数，又称为 next 数组。在计算 next 数组之前，首先我们需要明确两个概念: “前缀"和"后缀”:

“前缀"指除了最后一个字符以外，一个字符串的全部头部组合
“后缀"指除了第一个字符以外，一个字符串的全部尾部组合

1
2
3
4
5
6
7
8


以"ABCDAB"为例
0.　"A"的前缀和后缀都为空集，共有元素的长度为0；
1.　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
2.　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
3.　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
4.　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
5.　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
6.　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

即"ABCDAB” 的 next 数组为 [0, 0, 0, 0, 1, 2, 0]。其中

next 数组的下标对应每个前缀子串结尾字符的下标
next 数组的值则是最长可匹配子串的长度

1.3 KMP 复杂度分析

KMP 的空间复杂度是 O(m)，时间复杂度为 O(m+n)。分析过程在我们讲解完 KMP 的实现之后再来讲解。

2. KMP 算法实现

2.1 计算部分匹配表

部分匹配表的计算非常巧妙，下面是代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


def kmp_next(P):
    m = len(P)
    fail = [0] * m
    j = 1  # 按照下标从小到大的子串
    k = 0  # 上一个子串最长可匹配子串的长度
    while j < m:
        if P[j] == P[k]:     
            fail[j] = k + 1
            j += 1
            k += 1
        elif k > 0:
            k = fail[k - 1]
        else:
            j += 1
    return fail

我们以"ABCDAB"为例来讲解计算过程，大家需要牢记的是P[j] 表示当前子串的最后一个字符，P[k] 表示上一个子串的最长可匹配子串的下一个字符，此时分为三种情况:

P[j] == P[k]: 对应ABCDAB，前一个子串是ABCDA，最长可匹配子串是 A，此时P[5]==P[1]==B，即AB=AB,所以 ABCDAB的最长可匹配子串长度就是 2
P[j] != P[k] and k > 0: 对应ABCDABD，P[6]!=P[2]，即D!=C，此时可以确定的是ABCDABD的最长可匹配子串，只能从ABD进行匹配，进而问题转换为已知AB的最长可匹配子串，求ABD的最长可匹配子串问题。
P[j] != P[k] and k == 0: 显然此时就没有任何可匹配到的子串。

这个计算过程很巧妙，不多看几次很难明白。

在next 的计算过程中，使用了一个额外的数组，因此这一部份的空间复杂度是 O(m)。在 while 循环中 j 执行的次数一定不会超过 m，而 k 变量无论是增加累计的量，还是减少累计的量都不会超过 m，因此这一部分的时间复杂度为 O(m)。

2.2 KMP 字符串匹配过程

字符串匹配的过程中，最重要的一步是确定不匹配时，后移的位数，代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


def kmp_match(T, P):
    fail = kmp_next(P)
    n, m = len(T), len(P)
    k = 0
    j = 0
    while j < n:
        if T[j] == P[k]:
            if k == m - 1:
                return j - (m - 1)
            k += 1
            j += 1
        elif k > 0:
            k = fail[k - 1]  # 后移表示为 k 索引的变化
        else:
            j += 1
    return -1

整个匹配过程中，j 变量的执行次数不会超过 n，而变量 k，无论是增加的累计量还是减少的累计量都不会超过 n，因此这一部分的时间复杂度不会超过 O(n)。因此总的时间复杂度不会超过O(m+n)。

参考:

目录