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

实验四：KMP算法实验报告一、 问题描述模式匹配两个串。二、 设计思想这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法：int Index(String S,String T,int pos)/参考数据结构中的程序 i=pos;j=1;/这里的串的第1个元素下标是1 while(i=S.Length & jT.Length) return i-T.Length;/匹配成功 else return 0;匹配的过程非常清晰，关键是当失配的时候程序是如何处理的？为什么要回溯，看下面的例子：S:aaaaabababcaaa T:ababcaaaaabababcaaa ababc.(.表示前一个已经失配)回溯的结果就是aaaaabababcaaa a.(babc)如果不回溯就是aaaaabababcaaa aba.bc这样就漏了一个可能匹配成功的情况aaaaabababcaaa ababc这是由T串本身的性质决定的，是因为T串本身有前后部分匹配的性质。如果T为abcdef这样的，大没有回溯的必要。改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。如果不用回溯，那T串下一个位置从哪里开始呢？还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：.ababd. ababc -ababc这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当Tj失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。数据结构上给了next值的定义： 0 如果j=1 nextj=Maxk|1kaaab -aaab -aaab像这样的T，前面自身部分匹配的部分不止两个，那应该往前跳到第几个呢？最近的一个，也就是说尽可能的向右滑移最短的长度。到这里，就实现了KMP的大部分内容，然后关键的问题是如何求next值？先看如何用它来进行匹配操作。将最前面的程序改写成：int Index_KMP(String S,String T,int pos) i=pos;j=1;/这里的串的第1个元素下标是1 while(i=S.Length & jT.Length) return i-T.Length;/匹配成功 else return 0;求next值，这也是整个算法成功的关键。前面说过了，next值表达的就是T串的自身部分匹配的性质，那么，我只要将T串和T串自身来一次匹配就可以求出来了，这里的匹配过程不是从头一个一个匹配，而是从T1和T2开始匹配，给出算法如下：void get_next(String T,int &next) i=1;j=0;next1=0; while(i=T.Length) if(j=0 | Ti=Tj)+i;+j; nexti=j;/*(2)*/ else j=nextj; 看这个函数非常像KMP匹配的函数！注意到(2)语句逻辑覆盖的时候是Ti=Tj以及i前面的、j前面的都匹配的情况下，于是先自增，然后记下来nexti=j，这样每当i有自增就会求得一个nexti，而j一定会小于等于i，于是对于已经求出来的next，可以继续求后面的next，而next1=0是已知，所以整个就这样递推的求出来了，方法非常巧妙。这样的改进已经是很不错了，但算法还可以改进，注意到下面的匹配情况：.aaac. aaaa. T串中的a和S串中的c失配，而a的next值指的还是a，那同样的比较还是会失配，而这样的比较是多余的，如果我事先知道，当Ti=Tj，那nexti就设为nextj，在求next值的时候就已经比较了，这样就可以去掉这样的多余的比较。于是稍加改进得到：void get_nextval(String T,int &next) i=1;j=0;next1=0; while(i=T.Length) if(j=0 | Ti=Tj) +i;+j; if(Ti!=Tj) nexti=j; else nexti=nextj;/消去多余的可能的比较,next再向前跳 else j=nextj; 三、 分析理论时间复杂性这个程序或许比想像中的要简单，因为对于i值的不断增加，代码用的是for循环。因此，这个代码可以这样形象地理解：扫描字符串S，并更新可以匹配到T的什么位置。为什么这个程序是O(n)的？ KMP的时间复杂度分析可谓摊还分析的典型。我们从上述程序的j 值入手。每一次执行while循环都会使j减小（但不能减成负的），而另外的改变j值的地方只有第五行。每次执行了这一行，j都只能加1；因此，整个过程中j最多加了n个1。于是，j最多只有n次减小的机会（j值减小的次数当然不能超过n，因为j永远是非负整数）。这告诉我们，while循环总共最多执行了n次。按照摊还分析的说法，平摊到每次for循环后，一次for循环的复杂度为O(1)。整个过程显然是O(n)的。这样的分析对于后面P数组预处理的过程同样有效，同样可以得到预处理过程的复杂度为O(m)。四、 原程序和调试结果package kmp;public class kmp String s=aaaaaaaa; String p=aaaab; int next=new ints.length(); /主要计算next的值 void calnext() int i,j=0; next1 = 0; next0=-1; for(i=2;is.length();i+) if(s.charAt(j)=s.charAt(i-1) nexti=nexti-1+1;j+; else if(nextj0) nexti=0; else nexti=nextj; j=nexti; /输出实际运算次数 void display() int i=0,j=0,v; int count=0; while(is.length()&jp.length() if(s.charAt(i)=p.charAt(j) i+;j+; else if(j=0)i+; else j=nextj; count+; System.out.println(+count);