理解字符串匹配算法KMP

字符串匹配问题的基本形式是：在文本串 text 中，查找模式串 pattern 出现的位置。最朴素的做法是暴力匹配：一旦发生不匹配，就把模式串整体右移一位，重新从头比较。
这种方法的问题在于：已经比较过的字符被重复比较, 最坏时间复杂度是 O(nm). KMP（Knuth–Morris–Pratt）算法的核心目标只有一个：当匹配失败时，模式串尽可能向右跳，而不是回到起点。

理解 KMP 算法的过程

举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串”ABCDABD”？

### i = 1 ; q= 0
BBC ABCDAB ABCDABCDABDE
|
ABCDABD

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

### i = 2 ; q = 1
BBC ABCDAB ABCDABCDABDE
 |
 ABCDABD

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

### i = 5 ; q = 2
BBC ABCDAB ABCDABCDABDE
    |
    ABCDABD

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

### i = 6 ; q = 3
BBC ABCDAB ABCDABCDABDE
     |
    ABCDABD

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

### i = 11 ; q = 6
BBC ABCDAB ABCDABCDABDE
          |
    ABCDABD

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

1
2
3

BBC ABCDAB ABCDABCDABDE
     |
     ABCDABD

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

1
2
3

BBC ABCDAB ABCDABCDABDE
          |
    ABCDABD

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

搜索词	A	B	C	D	A	B	D
部分匹配值	0	0	0	0	1	2	0

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。

1
2
3

BBC ABCDAB ABCDABCDABDE
          |
    ABCDABD

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

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

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

### i = 11; q = 2
BBC ABCDAB ABCDABCDABDE
          |
        ABCDABD

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

### i = 11; q = 0
BBC ABCDAB ABCDABCDABDE
          |
          ABCDABD

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

### i = 18; q = 2
BBC ABCDAB ABCDABCDABDE
                 |
           ABCDABD

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

### i = 18; q = 7
BBC ABCDAB ABCDABCDABDE
                     |
               ABCDABD

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

部分匹配表的如何产生

搜索词	A	B	C	D	A	B	D
部分匹配值	0	0	0	0	1	2	0

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”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。

1
2
3

BBC ABCDAB ABCDABCDABDE
                 |
           ABCDABD

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

所以在写算法的过程中，我们无需回退查询字符串的坐标，一旦找到大于0的部分匹配值（注意，这里的部分匹配值其实指向的是重复字符串的最后一个字符，也就是说我们已经知晓它一定存在在查询字符串中），我们直接比较当前坐标对应的字符和部分匹配值对应的下一个字符是否匹配，然后循环回退（其实部分匹配值就是在模式字符串上不断回退的过程），最终直到找到完整的字符串。这样，整个寻找的流程的复杂度大大降低。其中构建部分匹配需要的复杂度为O(m)，而匹配过程的复杂度为O(n)，总复杂度为O(m+n)，相比较于朴素算法的O(mn)复杂度，KMP算法的效率大大提高。

KMP 算法的实现

构建部分匹配表

根据前面的描述，我们可以手动构建匹配表，代码如下：

function get_longest_intersaction(lst1::Set{Vector{Char}}, lst2::Set{Vector{Char}})::Int
    ints = intersect(lst1, lst2)
    common_len = 0
    if length(ints) == 0
        common_len = 0
    else
        common_len = maximum(length.(ints))
    end
    common_len
end

function partial_match_table_manually(pattern::Vector{Char})::Vector{Int}
    prefix, suffix = Set{Vector{Char}}(), Set{Vector{Char}}()
    pLen = length(pattern)
    Next = zeros(Int, pLen)
    push!(prefix, [pattern[1]])
    push!(suffix, [pattern[2]])
    ints = intersect(prefix, suffix)
    common_len = get_longest_intersaction(prefix, suffix)
    Next[2] = common_len
    for i = 3:pLen
        push!(prefix, pattern[1:(i-1)])
        empty!(suffix)
        for j = 2:i
            push!(suffix, pattern[j:i])
        end
        ints = intersect(prefix, suffix)
        common_len = get_longest_intersaction(prefix, suffix)
        Next[i] = common_len
    end
    Next
end

当然，我们还有更简单的算法构建该表，代码如下：

function partial_match_table(pattern::Vector{Char})::Vector{Int}
    pLen = length(pattern)
    Next = zeros(Int, pLen)
    k = 0
    for q = 2:pLen
        while k > 0 && pattern[k+1] != pattern[q]
            k = Next[k]
        end
        if pattern[k+1] == pattern[q]
            k += 1
        end
        Next[q] = k
    end
    Next
end

这个构建方法的原理和 KMP 算法的匹配过程是相同的，都是通过回退寻找部分匹配值。具体请见 KMP 算法：线性时间 O(n)字符串匹配算法。

KMP 算法的匹配过程

根据前面对算法的理解，我们的代码如下：

function KMP_match(text::T, pattern::T)::Vector{Int} where {T<:AbstractString}
    tLen, pLen = length(text), length(pattern)
    text_lst = collect(text)
    pattern_lst = collect(pattern)
    Next = partial_match_table(pattern_lst)
    q = 0
    idxs = Int[]
    for i = 1:tLen
        #println("i = $i")
        while q > 0 && pattern_lst[q+1] != text_lst[i]
            q = Next[q]
            #println("q_while = $q")
        end
        if pattern_lst[q+1] == text_lst[i]
            q += 1
            #println("q_if = $q")
        end
        if q == pLen
            push!(idxs, i-pLen+1)
            q = 0
        end
    end
    idxs
end

你可以手动取消掉println的注释，打印出每个循环的数值，来帮助你理解这个算法。另外，我已经在前面的详解步骤中添加了此刻i 和 q 的值，你可以和代码中的值对应起来。