本文从blog.163.com/kazenoyume@126/上迁移过来

最近在工作之余,参加了hihocoder推出的编程提高班。这个编程提高班真的很有意思,它的讲课内容是跟算法分析设计有关的。而这周讲课的内容,是大家都耳熟能详的KMP算法。
在大二的时候,我曾经学习过KMP算法,当时还刷了好几道OJ题,所以就理所当然的以为这周的算法题目是相当的简单,不需要花很多时间就能完成的了。但是当我开始做题目的时候,我却发现自己完全不懂KMP算法!当初学习KMP算法的时候,只是对算法有个直观上的了解,就只知道它的时间复杂度和空间复杂度,完全只把它当作API来用。而且当时学习的时候也是晕头转向的,总觉得KMP算法绕得太厉害了,一时半刻学不来,于是就没学了。
在写之前,我参考了好网上好几篇写KMP算法的文章。那些文章内容始终都觉得有点饶,不太适合自己的理解。但是自己又觉得自己还没有能力把这个算法说得清楚明白,简单明了。我想了下,既然别人的文章都叫做《详解KMP算法》,那我给自己的文章起个名字叫做浅尝KMP算法吧。要是大家看完之后,觉得还是没理解KMP算法的话,那我能说:“这只是浅尝KMP算法啊,不懂也很正常啊,大家就当是被我忽悠进来的吧:)”。

KMP算法介绍

给定两个字符串A和B,怎么样判断B是不是A的子串呢?
这问题相当简单,相信每一个学过编程语言的人都知道怎么解决这个问题。最简单的做法,就是粗暴(Brute Force,下文称为BF)的枚举A的所有可行下标i, 判断A[i, i+B.len-1]和B是否相等(B.len为B字符串的长度)。假设A和B的字符串长度分别为A.len和B.len,那么这种算法的时间复杂度为O(A.len * B.len)。当A和B比较小的时候还可以接受,但是当数据量比较大的时候效率就很低了。为了提高字符串的匹配算法,以前的计算机科学家们可真是前赴后继,集体跳坑研究出各种字符串算法,比如大名顶顶的trie tree。今天我们要介绍的主角可不是它,而是KMP算法。
KMP算法的全称是Knuth-Morris-Pratt,这三个英文单词是研究出这个算法的这三个大神的名字。相信大家对Knuth也不会陌生,他就是《计算机程序设计艺术》一书以及排版软件Tex的作者。而Morris是函数式编程思想的开山鼻祖之一,比如最近很流行的惰性计算就是它提出的。Pratt是Knuth的弟子,但是最牛逼的是他仅用了20个月就把博士学位拿到手了,简直是个天才啊。 KMP算法的核心思想是通过空间效率来换时间效率,它在进行字符串A和B匹配之前,需要先计算出B的一些特性,然后根据这些特性来优化匹配算法。KMP算法的时间复杂度是线性的,听起来非常诱人是不?

初探KMP

包括笔者在内,我相信大家在看网上的KMP算法时也是看得不太懂,总是云里雾里的,觉得这东西很悬乎。我在这篇文章里想给大家一个对KMP算法的初步印象,给大家一种感觉,希望大家在看完这篇文章后觉得,其实KMP算法也不难啊~ 刚才也说过了,BF算法正是由于过多地比较这些重复出现的字符串导致其效率比较低。假如在比较A和B字符串之前,我就知道哪些字符应该比较,哪些字符不应该比较,减少BF中重复比较字符串的次数,效率就自然提高了。 比如A=abababababb,B=abababb,BF需要进行的比较计算如下所示:
1.jpg
在上面这些比较里面可以看到,A和B的比较要不就是只差最后一位比较就成功了,要不就是完全不成功。而且A和B的比较过程中,第1~6轮 和第9~14轮和17~22轮的比较是非常相似的。那么我们是否能利用这些信息,在不匹配的时候让B向右位移一定的步数,使得A和B重新有部分匹配呢?利用这些信息来使B进行跳跃的就是KMP的核心思想了。

NEXT数组

在第二章中,说明了KMP的主要思想是利用字符串B自身的信息,在匹配的时候进行跳跃。保存这个匹配信息的就是NEXT数组。这个NEXT数组真的很作弊,它作弊的地方就在于,当它发现A和B不匹配的时候,它知道应该把B向右移动多少位来重新匹配。比如上面的例子中,B=abababb的NEXT数组是{0, 0, 1, 2, 3, 2, 0}。现在我们利用这个数组配合来讲解一下上面的KMP算法演示的例子。
在第1~6轮时,A和B字符串均匹配成功了。但是在第7轮的时候却失败了,当第7轮匹配失败的时候,应该去查阅NEXT[6],发现B字符串需要向右位移2位,此时位移两位之后,A[3, 6]和B[1, 4]还是匹配的。

        A=abababababb
位移前	B=abababb
位移后	B=__abababb

那么第8轮的时候就去比较A[7]和B[5],第9轮的时候比较A[8]和B[6]。当在第10轮的时候,发现A[9]和B[7]无法匹配,这时候继续查阅NEXT[6],将B字符串继续向右移动两位。移动两位之后,A[5, 8]和B[1,4]还是匹配的。

        A=abababababb
位移前	B=__abababb
位移后	B=____abababb

这时候继续进行匹配,直至匹配成功。
那么这个NEXT数组到底是什么呢?为什么能这么神奇呢?
一种合理的对NEXT数组的解释,是最长公共前后缀的数目。最长公共前后缀指的是,对于一个字符串S来说,找出最大的i,使得S[1, i] == S[S.len - i + 1, S.len](1 < i < S.len)。这里,S[1, i]指的是这个字符串的一个前缀,S[S.len - i + 1, S.len]指的是这个字符串的一个后缀。在知道NEXT数组数值的前提下,当发生字符串A和B不匹配的情况,就可以将B字符串向右位移<A和B已成功匹配字符串数目 - NEXT[A和B已成功匹配字符串数目]>这么多位。
网上基本上对NEXT数组的解释少之又少,在下一小节中,我尝试提出我自己的愚见。要是大家赶着用这个算法的话,那这一小节就可以跳过了吧。

NEXT数组的解释

我们再来重新看一下BF算法那个例子。并将所有成功匹配的地方凑起来,看看到底是什么。
2.jpg
在上图中,我把A和B两个字符串在第7轮比较中不匹配的地方劈了开来。可以看到在左面,当发生匹配成功的时候,第1~7轮的B和第9~14轮的B有公共字符串的部分,而且它也与第17~22轮的B有公共字符串的部分。当没有发生匹配成功时,它们之间没有公共的部分。那就是说,在劈开点之前,假如想通过向右移动B,来使A和B再次发生匹配在劈开点之前完全匹配的话,需要满足:
(1)设B和A已成功匹配了i个点,不匹配的地方是i + 1
(2)设j为将B向右移j步时,能使B和A在不匹配的地方之前有重新匹配的部分
(3)B[j + 1, i] == B[1, i - j]
(4)0 < j < i(0步时没有意义,i步时已经完全超过了劈开点,也没有意义)
在上面例子中i = 6, j = 2或4。此时,它们与A的公共匹配数分别为4和2。上述条件中的第3项中,B[1, i - j]是B[1, i]的一个前缀,B[j + 1, i]是B[1, i]的一个前缀。换句话说,第3点实际就是找出字符串B[1, i]的公共前后缀,j就是代表这个公共前后缀的长度。假如有了这个j,我们就可以知道B应该向右移动多少位了。

现在来思考一下为什么NEXT数组选择的是最长公共前后缀。假如一个字符串遇到了多种可行的跳跃方案时,比如上面例子(A=abababababb,B=abababb,i = 6, j = 2或4)这时候该如何选择呢?答案是选择j较小值者进行位移。
一种直观的解释,就是j是选择较大者进行位移的话,那么在位移过程中将会丢失一些有用的信息。当B从ababab的已匹配状态跳跃到ab的已匹配状态时,明显跳过了abab的已匹配状态,那么假如这时候遇到的A字符串不是abababababb,而是ababababbab,那匹配就失败了,显然选择大的进行跳跃的是不对的。
另外,选择较小的j进行位移的话,当下一步匹配失败的时候,还是可以迁移到选择较大的j进行位移的状态的。当存在有两个的j值j1和j2(j1 < j2)的时候,那么就会有以下两个条件成立:(1)B[1, j1] == B[i - j1 + 1, i](2)B[1, j2] == B[i - j2 + 1, i]。我们把这两个条件画个图,就知道为什么选择较小的j也可以迁移到选择较大的j的状态了。

3.jpg
当发生位移后,A和B匹配的字符为B[1, j2]。从图中可以看到,其实B[1, j1]的完全就是B[1, j2]的公共前后缀里面的前缀,当B[j2 + 1]和A再次发生不匹配的时候,B完全是可以迁移到B[1, j1]和A匹配的状态的。至此,证明了选择较小的j的有效性,也证明了为什么NEXT数组记录的是最长公共前后缀而不是随便挑一个数了。(当j有超过两个以上的时候证明类似,当j1<j2<j3<…<jn时,每次只证明相邻的两个即可)

至此,总结了KMP如何使用NEXT数组的方法,KMP的主函数就可以写出来了:

METHOD KMP:
j = 0 #A和B已成功匹配的字符串数目
FOR i = 1 TO A.len:
    WHILE j > 0 && A[i] != B[j + 1]: j = NEXT[j]
    IF A[i] == B[j + 1]: ++ j
    IF j == B.len: j = NEXT[j] #已找到匹配的地方,重新匹配

NEXT数组的计算

刚开始时,笔者也只是想到O(n^3)的算法。但是看了网上的各种讲解之后,才发现它是一个递推问题。
NEXT数组的计算是这样的,要计算NEXT[i]时,可利用NEXT[1],…, NEXT[i-1]的信息进行计算。考虑NEXT[i]和NEXT[i-1],有以下几种情况:
(1)NEXT[i - 1]不存在(NEXT[i - 1] == 0),若B[1] == B[i] (i != 1)时,NEXT[i] = 1,否则为0。
(2)NEXT[i - 1]存在,且B[1, NEXT[i - 1]] == B[i - NEXT[i - 1], i - 1],此时,若B[NEXT[i - 1] + 1] == B[i],即说明B[1,i]的最长公共前后缀可以从B[1,i-1]计算而出,此时NEXT[i] = NEXT[i-1] + 1。
(3)NEXT[i - 1]存在,且B[1, NEXT[i - 1]] == B[i - NEXT[i - 1], i - 1],但B[NEXT[i - 1] + 1] != B[i]。此时,即说明无法通过扩展B[1, i-1]的最长公共前后缀来计算出NEXT[i]。
第一和第二种情况都比较好理解,而第三种情况理解起来可能就比较麻烦了。
4.jpg
下面我以B=abdabcabdabd为例子,讲解第三种情况的时候该如何计算NEXT数组。
当i=12的时候,NEXT[11] = 5,但是由于B[12] != B[NEXT[11] + 1],无法把第2种情况应用上去。当发生这种情况的时候,B[1,12]的最长公共前后缀串必然不会比NEXT[11]大,否则将不会出现这第3种情况。现在可以知道B[1,12]的最长公共前后缀串必然在[1, NEXT[11]]这个区间。倘若要找出一个k,使得B[1, k]和B[12-k+1, 12]相等,这个i就必然会落在[1,NEXT[11]]这个区间。在这个例子中,这个k为3,我们来看看当k=3的时候,到底发生了什么神奇的事情。
5.jpg
从上图可以看出,B[1,11]和B[1,12]的最长公共前后缀有公共的部分。NEXT[12]的前缀与NEXT[11]的前缀有公共的部分,NEXT[12]的后缀又和NEXT[11]的后缀有公共的部分。倘若抛开NEXT[12]中的d,将其染成灰色,再来看看是怎么样的。
6.jpg
现在可以看到,除去d这部分,NEXT[12]的后缀是包含在NEXT[11]的后缀里面的。由于NEXT[11]的前缀和后缀是相等的,即B[1,5]=B[7,11],所以NEXT[12]的后缀(去除d部分)完全可以在B[1,5]字符串的后面几位找到。NEXT[12]的前缀(去除d部分)也可以从NEXT[11]的前几位找到。假如去除d部分的话,NEXT[12]所找的公共前后缀是在NEXT[11]的前缀里面找的。同时,我们在找k的时候,总是希望k尽可能的大,即B[1,12]的公共前后缀尽可能的大,也就是找出B[1, NEXT[11]]里面的最长公共前后缀。
当找到B[1, NEXT[11]]的最长前后缀的时候,也就是找到NEXT[NEXT[11]]的时候,就需要判断B[NEXT[NEXT[11]] + 1]是否与B[12]相等,当相等的时候,NEXT[12] = B[1, NEXT[11]]中最长公共前后缀的数目 + 1 = NEXT[NEXT[11]] + 1。当不相等的时候,其实问题又再次转化回了第三种情况,只是此时借助的信息不是NEXT[11],而是NEXT[NEXT[11]]。
KMP构造部分伪代码如下:

METHOD compute_prefix
NEXT = array of size B.len
NEXT[1] = 0
FOR i = 2 TO B.len
    j = NEXT[i - 1]
    WHILE j > 0 && B[i] != B[j + 1]: j = NEXT[j]
    IF j > 0: NEXT[i] = j + 1
    ELSE:NEXT[i] = B[i] == B[1] ? 1 : 0

在这里,对于第(1)和第(2)种情况来说,它们都能直接跳过代码中第五行的判断条件,从而直接到达最后的IF-ELSE判断。其中IF对应的是第(1)种情况,ELSE对应的是第(2)种情况。至于第(3)种情况,就需要在循环中作一定的处理后再作判断。

六. 结尾

好了,说了那么多废话终于写完了。第一次体会到写技术文章是多么辛苦,以前一直是做伸手党,以后要多写技术博客才行~

参考资料: