一眼看懂KMP匹配算法

时间:2024-07-16 20:34:02

KMP算法——快速从字符串M(母串)中找出与字符串Z(子串)匹配的子串

例1:

0 1 2 3 4 5

M:a b c a b d

Z:  a b d

BF算法(最一般的算法,也叫“蛮力算法”):

将Z[0]-M[0](用“-”表示比较),如果=,则Z[1]-M[1],...直到Z[i]!=M[i],回溯

然后Z[0]-M[1],同上方法~最常见的做法,很容易理解,可是效率比较低。

KMP算法:比较过的字符段也是有信息可以利用的。

如例1,Z匹配M到   Z[2]=d  !=  M[2]=c, 说明什么?说明前面Z[0]=M[0],Z[1]=M[1],一一对应相等。

然后需要回溯让Z[0]去和M[1]比较吗?其实没有必要

为什么? 看Z  =ab d    d前每个字符各不相同,既然 M=ab cxxxxxx(因为Z与M比较到d,对应的M前面的和Z一一对应相等,可以推测到M失配字符前面的字符),

BF算法是发现不匹配后让Z[0]=a回去和M[i](i=1,2,3...依次递增)比较,只有M[i]=Z[0],才有资格比较M[i+1]和Z[1],继续下一位比较下去,否则判断不等后直接就换下一位了,毫无意义。

但是我们研究了Z后发现  :   Z中d前面的字符(ab)串除了Z[0](a)外没有和Z[0]相同的了,那么由于M失配字符之前的字符都是和Z对应相同的,所以推测M失配之前的字符肯定没有与Z[0]相等的,所以他们都没有必要和M[0]去比较 直接可以拿Z[0]从失配点向后比较就可以了。

好吧,我们发现Z上面还是有点信息的(重点理解红字的意思),但还是有点模糊

例2:    0 1 2 3 4 5

M:a b c a b d e a f a f

Z:  a b c a b e

看例2.明显Z[5]与M[5]失配。只需要看Z就能推测出M[0]~M[4]是什么。而我们失配之后,下一次匹配比较的前提就是M[i]=Z[0](i=1,2,3....),所以看Z匹配部分

a b c a b  ,推测出M对应的M[3]M[4]=ab,下次可以从M[3]开始匹配,有成功可能性。但是如果换成 如下

0 1 2 3 4 5

M:a b c a d d e a f a f

Z:  a b c a d e

Z=a b c a d 虽然Z[3]=Z[0],但明显Z[4]!=Z[1],依然无法匹配,所以我们发现只有Z失配字符前呈现abxxab类型,才可从M对应ab处开始下一次监测匹配,否则M失配前的字符均无法匹配Z(如例1所示),所以也无需进行判断。

所以下一步我们只要知道Z匹配比较到第n位,那么我们通过分析Z的前n-1的字符串,分析它们的对称性,就可以判断出对应M下次开始比较的位置。

数据结构语言只是工具,关键是解决问题的思想。

这就是基本思想,具体代码网上随处可见,就不继续写了,表达可能还是不太清楚,多看两遍理解了思想,就豁然开朗了。

后面补充一种其他算法思想:

RK算法:

一个字符一个字符的比较会不会有点慢呢?

如果把n个字符的Z当成一个数z,把M的n个连续字符子串也当成一个数m。

那么如果z!=m,则M对应的该子串肯定和Z不同;反之,z=m就有很大可能相同了,只需要在一个较小的范围内逐个字符比较就好,反正又不多。

M:a b c a b d e a f a f     m=abcabd

Z:  a b c a b e                  z=abcabe

不等?m=bcabde(向后移动一位),继续比较,直到m=z,然后比较Z和M子串。其实挺快的这个方法~具体代码网上找