文档介绍：搜了网上很多KMP的代码下来调试,发现不是下标越界,就是死循环的,相当诡异...最后重新拿起严老师那本《数据结构》来翻,各种费解,有个地方用下标值和字符串下标0的元素做判断,更是诡异了...
过了一天,忽然觉悟了。网上这些代码都是来自《数据结构》或者和他同源的版本的,而它使用的是以下标1为起始的字符串!对这种字符串组织格式,下标0存放的是字符串的长度。
可是如今主流的语言,几乎都是用的下标0作为起始,书本上的代码显然没法用,那就自己重写一个吧。
 
算法的原理
字符串匹配嘛,无非就是两个指针,分别指向主串和模式串,然后依次往后移,检查是否一致。http://fzl. 在遇到不能匹配的情况时(简称“失配”),一般的方法,就是让两个指针回溯,主串指针往后再移动一位,从头开始匹配。这其中做了很多重复劳动,我们可以分析一下:
可以看到模式串在匹配到下标5时失配了。
我们抓出模式串和主串在前方匹配的5个字符,并在模式串部分的前端和主串部分的后端找到了一对最长的相等的字串(不等于原来的串),用阴影标记一下,后面有用。
接着移动模式串,继续匹配:
看出什么规律了么?每次比较,其实都是“abaab”的前端和后端的字串进行比较:
第一回是"abaa"vs"baab"
第二回是"aba"vs"aab"
第三回是"ab"vs"ab"
可见,只有在模式串部分的前端和主串部分的后端重合的时候,才可能继续匹配。
是这样么?当然是的,因为我们之前找出的是最长的,相等的字串!
这样就能把中间无效的对比步骤省略,主串的指针不变,模式串的指针直接跳到下标2继续匹配。这里的下标2就等于最长相等字串的长度。
接着推广到更一般的情形:
假设主串s,模式串patten,s和patten分别在下标i,j处失配,
如果j>0,那么,
显而易见,'si-k...si-1' = 'patten0...pattenk-1',此串长度为k,故下一步模式串指针应当跳转到下标k继续匹配。
在这里,http://youximingzhi. 因为'si-k...si-1' = 'pattenj-k...pattenj-1',得到'patten0...pattenk-1' = 'pattenj-k...pattenj-1',所以给定patten和j的情况下,k的值也是固定的。
如果j=0,那么i应当往后挪一位,j不变,重头匹配
至此,对于给定的patten,可以得到一个j->k的映射关系,记为数组next,其中,k = next[j]:
next[j] = Max{ k | 0<=k<j 并且 'patten0...pattenk-1' = 'pattenj-k...pattenj-1' }
当且仅当j == 0时,next[j] = -1(-1其实是没有意义的,在这里为了计算方便)
 
依照这个定义,已经可以写出一个计算next的弱弱的实现了。不过我先买个关子,先把主串的匹配搞定再说。
 
主串匹配算法
有了之前的分析,主串匹配的代码基本就可以一蹴而就了(Java代码):
static int Kmp(String s, String patten) {
int i = 0, j = -1;
int[] next = GetNext(patten