模式匹配KMP算法实验报告.doc

《模式匹配KMP算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验四：KMP算法实验报告一、问题描述模式匹配两个串。二、设计思想这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法：intIndex(StringS,StringT,intpos)//参考《数据结构》中的程序{ i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length&&j<=T.Length) {   if(S[i]==T[

2、j]){++i;++j;}   else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length)returni-T.Length;//匹配成功 elsereturn0;}匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子：S:aaaaabababcaaa T:ababcaaaaabababcaaa   ababc.(.表示前一个已经失配)回溯的结果就是aaaaabababcaaa    a.(babc)如果不回溯就是aaaaabababcaa

3、a       aba.bc这样就漏了一个可能匹配成功的情况aaaaabababcaaa     ababc这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。如果不用回溯，那T串下一个位置从哪里开始呢？还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：...ababd...  ababc  ->ababc这样i不用回溯

4、，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。《数据结构》上给了next值的定义：         0  如果j=1next[j]={Max{k

5、1

6、：T:aaab...aaaab...  aaab ->aaab  ->aaab   ->aaab像这样的T，前面自身部分匹配的部分不止两个，那应该往前跳到第几个呢？最近的一个，也就是说尽可能的向右滑移最短的长度。到这里，就实现了KMP的大部分内容，然后关键的问题是如何求next值？先看如何用它来进行匹配操作。将最前面的程序改写成：intIndex_KMP(StringS,StringT,intpos){ i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length&&j<=T.Length) 

7、{   if(j==0

8、

9、S[i]==T[j]){++i;++j;}//注意到这里的j==0,和++j的作用就知道为什么规定next[1]=0的好处了   elsej=next[j];//i不变（不回溯）,j跳动 } if(j>T.Length)returni-T.Length;//匹配成功 elsereturn0;}求next值，这也是整个算法成功的关键。前面说过了，next值表达的就是T串的自身部分匹配的性质，那么，我只要将T串和T串自身来一次匹配就可以求出来了，这里的匹配过程不是从头一个一个匹配，而是从T[1]和T

10、[2]开始匹配，给出算法如下：voidget_next(StringT,int&next[]){ i=1;j=0;next[1]=0; while(i<=T.Length) {   if(j==0

11、

12、T[i]==T[j]){++i;++j;next[i]=j;/**********(2)*/}   elsej=next[j]; }}看这个函数非常像KMP匹配的函数！注意到(2)语句逻辑覆盖的时候是T[i]==T[j]以及i前面的、j前面的都匹配的情况下，于是先自增，然后记下来next[i]=j，这样每当i有自增就会求得一

13、个next[i]，而j一定会小于等于i，于是对于已经求出来的next，可以继续求后面的next，而next[1]=0是已知，所以整个就这样递推的求出来了，方法非常巧妙。这样的改进已经是很不错了，但算法还可以改进，注意到下面的匹配情况：...aaac...  aaaa.T串中的'a'和S串中的'c'失配，而'a'的ne