KMP
基本介绍
KMP算法由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)
字符串的前缀和后缀
如果字符串A和B,存在A=BS,其中S是任意的非空字符串,那就称B为A的前缀。例如,”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”},我们把所有前缀组成的集合,称为字符串的前缀集合。 同样可以定义后缀A=SB, 其中S是任意的非空字符串,那就称B为A的后缀,例如,”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”},然后把所有后缀组成的集合,称为字符串的后缀集合。要注意的是,字符串本身并不是自己的后缀。
部分匹配表
KMP算法的核心,是一个被称为部分匹配表(Partial Match Table)的数组。我觉得理解KMP的最大障碍就是很多人在看了很多关于KMP的文章之后,仍然搞不懂PMT中的值代表了什么意思。这里我们抛开所有的枝枝蔓蔓,先来解释一下这个数据到底是什么。
对于字符串“abababca”,它的PMT如下表所示
PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。例如,对于”aba”,它的前缀集合为{”a”, ”ab”},后缀 集合为{”ba”, ”a”}。两个集合的交集为{”a”},那么长度最长的元素就是字符串”a”了,长 度为1,所以对于”aba”而言,它在PMT表中对应的值就是1。再比如,对于字符串”ababa”,它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”},它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}, 两个集合的交集为{”a”, ”aba”},其中最长的元素为”aba”,长度为3。
算法原理
在主字符串"ababababca"中查找模式字符串"abababca",从起始位置开始匹配也是采用bf(brute force),当主字符串匹配到i位置和模式字符串不匹配,此时模式字符串移动到j位置,如下图所示,
此时主字符串前j位和模式字符串的前j位相同,那么模式字符串指针j之前的后PMT[j-1]位与主字符串指针i之前的后PMT[j-1]位是相同的,又由于pmt的性质,模式字符串j指针之前的的后pmt[j-1]位与模式字符串的前pmt[j-1]位相同,所以主字符串中i指针之前的PMT[j−1]位就一定与模式字符串的第0位至第 PMT[j−1]位是相同的。这样一来,我们就可以将这些字符段的比较省略掉。具体的做法是,保持i指针不动,然后将j指针指向模式字符串的PMT[j −1]位即可。如下图所示
next数组
如果在j位失配,那么影响j指针回溯的位置的其实是第j−1位的PMT值,所以为了编程的方便, 我们不直接使用PMT数组,而是将PMT数组整体向后偏移一位,第0位赋值-1(没有实际意义,纯粹为了编程方便)。我们把新得到的这个数组称为next数组。如下图所示
如何构建next数组?
求next数组的过程完全可以看成字符串匹配的过程,即以模式字符串为主字符串,以模式字符串的前缀为目标字符串,一旦字符串匹配成功,那么当前的next值就是匹配成功的字符串的长度。
具体来说,就是从模式字符串的第一位(注意,不包括第0位)开始对自身进行匹配运算。 在任一位置,能匹配的最长长度就是当前位置的next值。如下图所示(i是next数组的下标,j是模式字符串的下标)
下面关键的地方
当i=7,j=4, p[i]=‘c’, p[j]=‘a’, 此时next[7]等于多少?
我们用图片来描述这个问题, 橙色的A表示已经确定的最长公共序列,此时i坐标对应的值为绿色的T将要与开头的A后面的元素进行比较。
如果比对失败,我们需要寻找次长公共序列B,然后T再与开头的B后面元素进行比对,依次类推直到T跟p[1]进行比较也不通过,那么next[i]=0;
我们看到,三幅图中,橙色块都是相等的,
如果存在次长公共序列,第二幅图表明,橙色块必然同时以B开头且以B结尾。
即,如第三幅图所示,
这表明,T位置的次长公共序列长度,就是橙色块的最长公共序列长度。
所以,next[7]的计算逻辑如下,i=7,j=4
p[i]和p[j]比较, 相等则next[i]=j
否则p[7]和p[next[4]]比较, 也就是p[7]和p[2]比较, 不相等, 再和p[next[2]]即p[0]比较,不相等, 此时才可以断定next[7]=0
代码如下:
|
|
完整代码
|
|