kmp

Posted on In

KMP算法用于做字符串匹配, 是计算机中经常用到的算法. 大多数都文章比较难懂, 这里参考了阮一封的博客文章, 比较通俗易懂, 但是没有详细解释Next表怎么具体算出来, 只是给出了概念的解释. 这里给出更完整的算法实现和解释.

基本思想

KMP的基本思想非常简单, 举例来说, 现在判断字符串”ABCDABD”是否在字符串”BBC ABCDAB ABCDABCDABDE”中.

img

首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

img

因为B与A不匹配，搜索词再往后移。

img

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

img

接着比较字符串和搜索词的下一个字符，还是相同。

img

直到字符串有一个字符，与搜索词对应的字符不相同为止。

img

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把”搜索位置”移到已经比较过的位置，重比一遍。

img

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。

img

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

img

已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此按照下面的公式算出向后移动的位数：

　　移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4，所以将搜索词向后移动4位。

img

因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

img

因为空格与A不匹配，继续后移一位。

img

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

img

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

img

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。

img

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

　　－　“A”的前缀和后缀都为空集，共有元素的长度为0；

　　－　“AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；

　　－　“ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

　　－　“ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

　　－　“ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；

　　－　“ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；

　　－　“ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

img

“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。

####算法实现

从上述思想来看, KMP的核心在于计算Next(部分匹配表)表, 其他的就是按照一个公式去移动而已. 我们来看看这个表用算法如何构造. 从15我们知道, Next就是”部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度.

我们先用最直观的做法来写这段代码, 然后再来优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func Next(str string) []int {
    length := len(str)
    next := make([]int, length) // next数组
    for q := 1; q < length; q++ {
        m := 0
        for k := 0; k < q; k++ {
            if str[:k+1] == str[q-k:q+1] && k+1 > m{ //如果前缀等于后缀, 并且长度是最长的, 就替换m
                m = k+1
            }
        }
        next[q] = m // m是写入next数组, 循环q
    }
    return next
}

这段代码将next数组计算出来, 符合正常的code思路, 但是复杂度是O(n^2), 显然不符合KMP的思想. 我们来做一些优化. 首先, 按照next的特性, 每次不需要回溯到0, 而是充分利用next特性回溯到已经匹配的字串, 如果不中再去找上一个, 算法见:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func Next(str string) []int {
    length := len(str)
    next := make([]int, length)
    next[0] = 0 // 初始化为0, 表示没有
    for q := 1; q < length; q++ {
        k := next[q - 1] // 只需要退回到前一个的next[q-1]位置, 而不用回到0
        for k > 0 && str[k] != str[q] { // 如果后一个位置不相等, 再往前回溯
            k = next[k] // 为什么这里不直接跳回到0呢, 因为next[k]表示前面已经匹配的, 而不需要退到起点, 先从最大长度往前回溯
        }
        if str[k] == str[q] {
            // 如果下一个字符相等, 将将k + 1, 由于前面的字串肯定是相等的, 不需要在比较
            next[q] = k + 1
        } else {
            next[q] = 0 // 如果不相等
        }
    }
    return next
}

改进后的算法时间复杂度为O(2n)

这种写法看起来不是很美观, 但是可读性更强, 有点写法会将初始值为-1, 然后将k := next[q - 1] 和 k = next[k]合在一起, 把 next[q] = k + 1和 next[q] = 0也合在一起, 这种”炫技” 行为我个人是非常不喜欢的, 看起来简洁但是将算法思想隐藏了, 可理解性很差. 同样我也不喜欢用任何lamda写法, 除非语言层面对此有性能优化, 否则只是用来恶心看代码的人.

按照这个思想写KMP的算法就非常简单了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func kmp(str1, str2 string) bool {
    next := Next(str2)
    i := 0 // i 是str1的index
    j := 0 // j 是str2的index
    length := len(str1)
    for i < length {
        if str1[i+j] == str2[j] {
            j++
            if j == len(str2) {
                // 完全匹配
                return true
            }
            continue
        }
        if j == 0 { // j==0 字节i++ 跳过
            i++
        } else {
            i = i + j - next[j-1]//移动位数 = 已匹配的字符数 - 对应的部分匹配值
            j = next[j - 1] // j回溯到记录位置
        }
    }
    return false
}

KMP算法的复杂度为O(M+N), 其他写法会更简洁, 但是同样为了可读性, 情愿写的罗嗦一点.

1
2
3
4
5
func main() {
    str1 := "BBC ABCDAB ABCDABCDABDE"
    str := "ABCDABD"
    fmt.Println(kmp(str1, str))
}

带上术例子进行计算, 总共循环次数为15次, 其中计算next数组总共只计算了7次.