标签归档:KMP

简单理解KMP算法

点击量:270

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),发现并不匹配。[……]

继续阅读