KMP算法是解决字符串匹配的常用算法之一,也就是在主串(比如aabbccdd)中的子串(bc)定位问题。子串称为P,如果它在一个主串称为T中出现,就返回它的具体位置,我们先来看看普通的字符串匹配是怎么做的
最基础的匹配
思路:
当匹配到如图第四个字符位置后,匹配失败,子串后移,继续匹配
第一位匹配失败,继续后移…
直到匹配成功
代码如下:
这种方式是效率最低,匹配次数最多的情况,接下来看KMP的解决思路
KMP中的PMT
KMP在遇到下图位置时,不会很无脑的把子串的j移动到第0位,主串的i移动到第1位,然后进行T[i]==P[j]的比较
因为从图上可以看得出,最好应该是直接让i不变,j==0,如下图
从这里开始匹配,省去了前面的几次无用匹配。
KMP思想:利用前面匹配的信息,保持i指针不变,通过修改j指针,让子串尽量地移动到有效的位置。
先用肉眼来看一下规律:
如图:C和D不匹配了,我们要把j移动到哪?显然是第1位。为什么?因为前面有一个A相同可以用:
再看一种:
可以把j指针移动到第2位,因为前面有两个字母是一样的:
我们可以看出来,匹配失败的时候,j变为k,j前面的的n个字符等于子串开头到k位置的n个字符的值
即:P[0 ~ k-1] == P[j-k ~ j-1]
这时我们发现规律了,其实就是要求当前j之前的字符串也就是ABCAB它的首尾对称的长度最大长度也就是PMT值。
PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。
所以上面最后一个图的情况下,j位置之前的字符串的PMT值为2,所以j的值变成2。
KMP之next数组
那么好了接下来核心就是next[j] = k,表示当T[i] != P[j]时,j应该变为k。
求next数组代码如下
通过上面代码可以直接算出j为0和1时的k,当j为0时,已经无法后退了所以设置为-1初始化值,当j为1时,它的前面只有下标0了,所以next[0]=-1,next[1]=0.
接下来就是两种主要情况了
第一种p[j] == p[k]
p[j] == p[k]时,有next[++j] = ++k;
因为当在p[j-1]处匹配失败后,j-1变为k-1,从k-1处重新开始匹配,原因就是他们共同有一个前缀A,所以当p[j] == p[k]后,他们就拥有了前缀AB所以k++;
第二种p[j] != p[k]
此时代码是:k = next[k];原因看下图
像上边的例子,我们已经不可能找到[ A,B,A,B ]这个最长的后缀串了,但我们还是可能找到[ A,B ]、[ B ]这样的前缀串的。所以这个过程就像在定位[ A,B,A,C ]这个串,当C和主串不一样了(也就是k位置不一样了),那当然是把指针移动到next[k]。
有了next数组之后就一切好办了,我们可以动手写KMP算法了:
KMP改进
KMP算法是存在缺陷的,来看一个例子:比如主串是aaaabcde,子串是aaaaax,next值为012345,当i=5时,如下图:
我们发现,当中的②③④⑤步骤,其实是多余的判断。由于子串的第二、三、四、五位置的字符都与首位的“a”相等,那么可以用首位next[1]的值去取代与它相等的字符后续next[j]的值,这是个很好的办法。因此我们对求next函数进行了改良。
领取专属 10元无门槛券
私享最新 技术干货