KMP字符串匹配算法.doc

KMP是一种著名的字符串模式匹配算法，它的名称来自三个发明人的名字。这个算法的一个特点就是，在匹配时，主串的指针不用回溯，整个匹配过程中，只需要对主串扫描一遍就可以了。因此适合对大字符串进行匹配。搜了网上很多KMP的代码下来调试，发现不是下标越界，就是死循环的，相当诡异.最后重新拿起严老师那本数据结构来翻，各种费解，有个地方用下标值和字符串下标0的元素做判断，更是诡异了.过了一天，忽然觉悟了。网上这些代码都是来自数据结构或者和他同源的版本的，而它使用的是以下标1为起始的字符串！对这种字符串组织格式，下标0存放的是字符串的长度。可是如今主流的语言，几乎都是用的下标0作为起始，书本上的代码显然没法用，那就自己重写一个吧。算法的原理字符串匹配嘛，无非就是两个指针，分别指向主串和模式串，然后依次往后移，检查是否一致。 在遇到不能匹配的情况时（简称“失配”），一般的方法，就是让两个指针回溯，主串指针往后再移动一位，从头开始匹配。这其中做了很多重复劳动，我们可以分析一下：可以看到模式串在匹配到下标5时失配了。我们抓出模式串和主串在前方匹配的5个字符，并在模式串部分的前端和主串部分的后端找到了一对最长的相等的字串（不等于原来的串），用阴影标记一下，后面有用。接着移动模式串，继续匹配：看出什么规律了么？每次比较，其实都是“abaab”的前端和后端的字串进行比较：第一回是abaavsbaab第二回是abavsaab第三回是abvsab可见，只有在模式串部分的前端和主串部分的后端重合的时候，才可能继续匹配。是这样么？当然是的，因为我们之前找出的是最长的，相等的字串！这样就能把中间无效的对比步骤省略，主串的指针不变，模式串的指针直接跳到下标2继续匹配。这里的下标2就等于最长相等字串的长度。接着推广到更一般的情形：假设主串s，模式串patten，s和patten分别在下标i，j处失配，如果j0，那么，显而易见，si-k.si-1 = patten0.pattenk-1，此串长度为k，故下一步模式串指针应当跳转到下标k继续匹配。在这里， 因为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 = nextj：nextj = Max k | 0=kj 并且patten0.pattenk-1 =pattenj-k.pattenj-1 当且仅当j = 0时，nextj = -1（-1其实是没有意义的，在这里为了计算方便）依照这个定义，已经可以写出一个计算next的弱弱的实现了。不过我先买个关子，先把主串的匹配搞定再说。主串匹配算法有了之前的分析，主串匹配的代码基本就可以一蹴而就了（Java代码）：static int Kmp(String s, String patten) int i = 0, j = -1; int next = GetNext(patten);/ 待实现 while (i s.length() & j j）处匹配时，此时可以得到nexti+1 = j+1如果j = 0时就失配了的话，自然nexti+1应当等于0至此，写出代码也就不难了，有些小技巧却要注意一下（Java代码）：static int GetNext(String s) int i = 0, j = -1; int next = new ints.length(); next0 = -1; / 这个初始化时必须的 while( is.length()-1) if( j = -1 | s.charAt(i) = s.charAt(j) i+; j+; n