简单理解KMP算法

Hits: 179

KMP是非常著名的字符串匹配算法,学生时代看了几遍都没有真正理解。偶然的,今天在微博上看到有人在哔哩哔哩上直播讲解KMP,看完之后觉得没讲到点子上,他只是教你怎么使用,却没有说出为什么要这么做。
网上关于KMP算法的介绍太多了,我就不再写了,可以先看完这几篇文章:
字符串匹配的KMP算法-阮一峰
(原创)详解KMP算法-孤影
KMP算法的Next数组详解-北京小王子
看完之后感觉自己好像是理解了,但是又总感觉没有真正理解。直到某一个瞬间突然灵光乍现,豁然开朗!我们知道,KMP有个重要的概念是要构造查询串的前缀和后缀,然后通过一个next数组来移动指针,以加快匹配效率。
但是为什么要构造前缀和后缀呢?
string_match
如上图所示,当我我们移动到红圈位置时,发现C和D是不一样的,这时候蛮力的做法就是把下面的字符串一个个往右移,但这样做效率并不高。仔细观察一下会发现:C和D之前的最长公共子序列肯定是一样的(也就是上图的ABCDAB),我们定义上面的为X,下面的为Y。现在想象一下:X不动,Y开始向右移动1个长度,那么匹配的就是X的后5位(BCDAB)和Y的前5位(ABCDA),发现并不匹配。那么我们再移动一个长度,匹配的就是X的后4位(CDAB)和Y的前4位(ABCD)发现也不匹配。以此类推,直到我们移动4个长度,匹配的就是X的后两位(AB)和Y的前两位(AB),这时候发现两者是一样的,这样就匹配成功了。这是我们一步一个长度移动的匹配过程,然而实际上我们可以直接算出来应该移动的位置。怎么算呢?我们的目标是匹配X的后n位和Y的前n位(如果存在这样的n的话),因为X和Y是相等的,所以X的后n位和Y的后n位是一样,那么问题就变成匹配Y自身的前n位和后n位。于是,聪明的几位大神们就这样引入了前缀和后缀的概念,什么是一个字符串的前缀和后缀呢?举个例子:对于字符串ABCDAB而言,它的前缀就是:A/AB/ABC/ABCD/ABCDA;后缀就是:BCDAB/CDAB/DAB/AB/B。这时我们会发现前缀和后缀的最长相同元素为AB,长度是2!于是我们构建一个叫做prefix table的东西,key就是当前字符的下标,value表示这个字符之前的字符串的最长公共前后缀的长度。比如对于字符串ABCDABD中的最后一个字符D而言,它的key就是6,value就是2。得到这个表之后,当遇到字符不一样时,就读取它的prefix table的值,然后把指针向右移动(已匹配的字符串长度 - 最长公共前后缀的长度)也就是 6 - 2 = 4即可。
这种算法之所以能够提高效率,主要得益于两个点:
1、上面的指针不需要回溯
2、可以一次移动多个字符

那么如何计算这个prefix table(next数组)呢?

我们直接先从代码入手,Java版本的代码是这样的:

这段代码看上去非常简洁,然而理解起来却是比较困难的,主要在于这段逻辑:

为什么p[i] != p[k]时,k = next[k]呢?这行代码所表达的意思就是:一旦匹配失败,则寻找到上一次匹配好的最长的公共前后缀,使之与p[i]再次比较。

这句话很难理解,我可以先看下面的一个例子:

当D和X不相等时,我们该怎么办呢?我们发现上图中两块绿茶色的字符串是相等的,那么第一块绿茶色的字符串已经匹配好的最长的前缀P[0, next[k]],必然等于第二块绿茶色的字符串的某一个后缀(示例中则是AB)!因此我们只要把k移动到next[k]处,再进行匹配next[k]的下一个元素P[next[k] + 1]和P[i]即可,然后我们发现匹配成功,于是两个指针都向前移,以此类推。


One thought on “简单理解KMP算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注