资源描述
实验四:KMP算法实验报告一、问题描述模式匹配两个串。二、设计思想这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。注意到这是一个改进的算法,所以有必要把原来的模式匹配算法拿出来,其实理解的关 键就在这里,一般的匹配算法:int Index(String S,String T,int pos)/参 考数据结构中的程序i=pos;j=1;/这里的串的第1个元素下标是1while(i=S.Length & jT.Length) return i-T.Length;/匹 配成功else return 0;匹配的过程非常清晰,关键是当失配的时候程序是如何处理的?为什么要回溯,看 下面的例子:S:aaaaabababcaaa T:ababcaaaaabababcaaaababc.(.表示前一个已经失配)回溯的结果就是aaaaabababcaaaa.(babc)如果不回溯就是aaaaabababcaaaaba.bc这样就漏了一个可能匹配成功的情况aaaaabababcaaaababc这是由T串本身的性质决定的,是因为T串本身有前后部分匹配的性质。如果T为a bcdef这样的,大没有回溯的必要。改进的地方也就是这里,我们从T串本身出发,事先就找准了丁自身前后部分匹配的位 置,那就可以改进算法。如果不用回溯,那T串下一个位置从哪里开始呢?还是上面那个例子,T为ababc,如果c失配,那就可以往前移到aba最后一个a的位 置,像这样:.ababd.ababc-ababc这样i不用回溯,j跳到前2个位置,继续匹配的过程,这就是KMP算法所在。这个当 Tj失配后,j应该往前跳的值就是j的next值,它是由T串本身固有决定的,与S串无 关。数据结构上给了 next值的定义:0如果j=1nextj = Maxk|1kaaab-aaab-aaab像这样的T,前面自身部分匹配的部分不止两个,那应该往前跳到第几个呢?最近的一 个,也就是说尽可能的向右滑移最短的长度。到这里,就实现7KMP的大部分内容,然后关键的问题是如何求next值?先看如何用 它来进行匹配操作。将最前面的程序改写成:int Index_KMP(String S,String T,int pos)i=pos;j=1;/这里的串的第1个元素下标是1while(i=S.Length & jT.Length) return i-T.Length;/匹配成功else return 0;求next值,这也是整个算法成功的关键。前面说过了,next值表达的就是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+;elseif(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);public static void main(String args) / TODO code application logic herekmp k=new kmp();k.calnext();k.display();五、对结果的分析进行了 12次匹配,匹配成功。
展开阅读全文