[置顶] 从朴素的字符串匹配算法到KMP算法

最初的计算机被用于科学的数值计算，算是一个计算能力很强的计算器。但随着计算机的发展，非数值计算的功能越来越多，于是就有了字符串。而所谓的KMP算法则是一种高效的字符串匹配算法，其名字取自三个发明人的名字：Knuth、Morris、Pratt，为了纪念他们，称之为Knuth-Morris-Pratt算法，简称KMP算法。

说KMP算法重要是因为字符串匹配应用广泛，而当数据量很大时，算法的效率就很关键了。当然字符串匹配算法还有Rabin-Karp、有限自动机等方法，这两种方法都不如KMP，故这里只讲KMP。

所谓的字符串匹配就是在一个长字符串中找一个短字符串，看长字符串中是否存在短字符串，若存在则返回出现的第一个位置，若不存在则返回一个标记。

先看朴素的字符串匹配算法的过程：

算法规则：i、j对应字符相等则i、j分别加1，不等则i、j分别回朔

最坏时间复杂度：O((n-m+1)*m)，假设n为长字符串长度，m为短字符串长度。最坏情况举例：aaaaaaaab和aaab匹配。

O((n-m+1)*m)的复杂度能不能优化呢，观察步骤4：

假设预处理过短字符串，知道短字符串中的首字符A!=B，A!=C，

而长字符串中的B、C和短字符串中的B、C却是相等的，故短字符串的A和长字符串的B、C肯定是不等的，即其实不需要步骤5和步骤6，可以直接从步骤4跳到步骤7，这就是所谓的KMP算法了。

这一样例中短字符串首字符(A)与之后的字符(B,C,E)均不相等，有点特殊，那么更一般的如果之后的字符中也有首字符会怎么样呢。一试遍知：

观察步骤5：

同样假设预处理过短字符串，那么我们可以事先知道短字符串中的首字符A0!=B1，A0==A2，B1==B3

而且：

1.长字符串中的B1和短字符串中的B1相等，故短字符串的A0和长字符串的B1肯定不等，故不需要步骤6。

2.长字符串的A2、B3分别与短字符串的A2、B3相等，故短字符串的A0、B1与长字符串的A2、B3肯定相等，故不需要步骤7、步骤8。

故可以直接从步骤5跳到步骤9。

总结两个例子，可以发现：

1.i不需要回朔：例一中步骤4(i=3)直接到步骤7(i=3)，例二中步骤5(i=4)直接到步骤9(i=4)

2.j按一定规律跳转，这个规律由短字符串预处理的结果决定：例一中步骤4(j=3)直接到步骤7(j=0)，例二中步骤5(j=4)直接到步骤9(j=2)

到此为止，KMP可以概括为：

当i、j对应的字符相等时，i++，j++

当i、j对应的字符不等时，i不变，j按预处理结果跳转

然后问题来了，如何对短字符串预处理？这也是KMP的难点，下面就来搞定它。

记号规定：

P[1..n]表示长度为n的字符串

P(k)表示字符串长度为k的前缀P[1..k]

π[q]为字符串的前缀函数，表示P[1..q]的前缀与后缀的最大匹配数，π[q] = max { k : k < q and P(k)是P(q)的后缀 }

π*[q]表示P[1..q]的前缀与后缀的所有匹配数，π*[q] = { k : k < q and P(k)是P(q)的后缀 }

π2[q] = π[π[q]],π3[q]=π[π[π[q]]]，以此类推

再次观察例二的步骤5：

当i=4,j=4时，两个对应的字符'C'和'E'不等，如果我们人自己去做这个匹配的话，我们是可以知道我们需要的是长字符串的"ABAB"的后缀和短字符串的"ABAB"的前缀的最长匹配。因为2个"ABAB"相等，换句话说就是需要短字符串的"ABAB"的前缀与后缀的最长匹配。而这个"ABAB"可以概括为j对应的字符前面的字符串，或者说是前j个字符串，再或者说是短字符串的P[1..j]。

也就是说预处理做的就是得到每一个位置对应的P[1..j]的前缀与后缀的最长匹配数。

把字符串的每种前缀垂直右对齐列出来可以清楚的看出前缀与后缀的匹配情况：

这个例子中可以发现π*[q]是有迭代关系的：π*[q] = {π1[q], π2[q], π3[q], ..., πt[q]}，比如：

π*[8] = {6, 4, 2, 0}，（表示"ABABABABCA"的前8位"ABABABAB"的后缀分别于前6位"ABABAB"、前4位"ABAB"、前2位"AB"、前0位匹配），

6 = π[8] = π1[8]

4 = π[6] = π[π[8]] = π2[8]

2 = π[4] = π[π[6]] = π[π[π[8]]] = π3[8]

0 = π[2] = π[π[4]] = π[π[π[6]]] = π[π[π[π[8]]]] = π4[8]

上图的右边的黑色框框+箭头可以看出这种迭代关系的作用，即可以根据q = 1,2,...,n的顺序计算π[q]，比如：

知道π[2]就得到了π[4]，知道π[4]就得到了π[6]，知道π[6]就得到了π[8]

有了前面的基础后，来看最关键的引理：

P是长度为m的字符串，π是P的前缀函数。对q = 1,2,...,m，若π[q] > 0, 则π[q] - 1 ∈π * [q - 1]

解释：

假设π[q] = t，则表示P的前q位的后t位和P的前t位匹配，既然匹配，那么各去掉最右的字符也是匹配的，前q位去掉最右的字符就变成了前q-1位，前t位去掉最右的字符就变成了前t-q位，即前π[q] - 1位。也就是说前q-1位的后缀和前π[q] - 1位匹配，也就是说π[q - 1] 包含了π[1] - 1，π[q] - 1 ∈π * [q - 1]。

重要的推论：

π[q] = 0                           当π*[q - 1]为空

π[q] = 1 + π[q - 1]         当π*[q - 1]不为空

这个推论就是我们求π的方法了

compute-prefix-function(P)

m := length[P]
π[1] := 0
k := 0
for q := 2 to m  // 每次迭代开始时k都等于π[q - 1]，第一次迭代时k=π[2-1]=π[1]=0，以此来记住各变量的初始值！
    do while k > 0 and P[k + 1] != P[q]  // 从π[q-1]开始从大到小搜索k∈π*[q-1]的所有值，直到找到一个P[k+1] = P[q]
        do k := π[k]
    if P[k + 1] := P[q]
        then k := k + 1
    π[q] := k  // 找到了符合P[k+1]=P[q]的k则π[q]=k+1,没找到则k会收敛位0最后π[q]=k=0
return π

弄懂搞定如何预处理以后KMP就简单了：

KMP-matcher(T, P)

n := length[T]
m := length[P]
π := compute-prefix-function(P)
q := 0                                                    // 已匹配字符数
for i := 1 to n
    do while q > 0 and P[q+1] != T[i]                     // 对应字符不等时，i不变，q按预处理规则跳转
        do q := π[q]
    if P[q+1] = T[i]
        then q := q + 1                                   // 对应字符相等，则i++,q++
    if q = m                                              // 结束
        then print "Pattern occurs with shift" i - m
            q := π[q]

最后加上时间复杂度：

算法	预处理时间	匹配时间
朴素的字符串匹配算法	0	O((n-m+1)*m)
KMP	Θ(m)	Θ(n)