模式匹配KMP算法实验步骤.docx

《模式匹配KMP算法实验步骤.docx》由会员分享，可在线阅读，更多相关《模式匹配KMP算法实验步骤.docx（5页珍藏版）》请在三一办公上搜索。

1、一、问题描述模式匹配两个串。二、设计思想这种由和同时发觉的改进的模式匹配算法简称为K.MP算法。留意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法：intIndex(StringS,StringT,intPOS)参考数据结构中的程序(i=pos;j=l;这里的串的第1个元素下标是1while(i=S.Length&jT.Length)returniT.Length;匹配胜利elsereturn0;)匹配的过程特别清楚，关键是当失配的时候程序是如何处理的？为什么要回溯，看下面的例子：S:aaaaabababcaaaT:ababcaaaaabab

2、abcaaaababc.(.表示前一个已经失配)回溯的结果就是aaaaabababcaaaa.(babe)假如不回溯就是aaaaabababcaaaaba.be这样就漏了一个可能匹配胜利的状况aaaaabababcaaaababc这是由T串本身的性质打算的，是由于T串本身有前后部分匹配的性质。假如T为abcdef这样的，大没有回溯的必要。改进的地方也就是这里，我们从T串本身动身，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。假如不用回溯，那T串下一个位置从哪里开头呢？还是上面那个例子，T为ababc,假如C失配，那就可以往前移到aba最终一个a的位置，像这样：.ababd.ababc

3、-ababc这样i不用回溯，j跳到前2个位置，连续匹配的过程，这就是KMP算法所在。这个当Tj失配后，j应当往前跳的值就是j的next值，它是由T串本身固有打算的，与S串无关。数据结构上给了next值的定义：O假如j=lnextj=Maxklkaaab-aaab-aaab像这样的T,前面自身部分匹配的部分不止两个，那应当往前跳到第几个呢？最近的一个，也就是说尽可能的向右滑移最短的长度。到这里，就实现了KMP的大部分内容，然后关键的问题是如何求next值？先看如何用它来进行匹配操作。将最前面的程序改写成：intIndexKMP(StringS,StringT,intpos)(i=pos;j=l;

4、这里的串的第1个元素下标是1while(i=S.Length&j0的好处了elsej=nextj:/i不变(不回溯),j跳动if(jT.Length)returni-T.Length;匹配胜利elsereturnO;)求next值，这也是整个算法胜利的关键。前面说过了，next值表达的就是T串的自身部分匹配的性质，那么，我只要将T串和T串自身来一次匹配就可以求出来了，这里的匹配过程不是从头一个一个匹配，而是从Tl和T2开头匹配，给出算法如下：voidgetnext(StringT,int&next)i=l;j-Ojnextl=O;while(i=T.Length)(if(j=-0IITi=Tj

5、)+i;+j;nexti=j;/*(2)*)elsej=nextj;)看这个函数特别像KMP匹配的函数！留意到(2)语句规律掩盖的时候是Ti=Tj以及i前面的、J前面的都匹配的状况下，于是先自增，然后登记来nexti=j,这样每当i有自增就会求得一个nexti,而j肯定会小于等于i,于是对于已经求出来的next,可以连续求后面的next,而nextl=0是已知，所以整个就这样递推的求出来了，方法特别奇妙。这样的改进已经是很不错了，但算法还可以改进，留意到下面的匹配状况：d33C.aaaa.T串中的a和S串中的c失配，而a的next值指的还是a,那同样的比较还是会失配,而这样的比较是多余的，假如

6、我事先知道，当Ti=Tj,那nexti就设为nextj,在求next值的时候就已经比较了，这样就可以去掉这样的多余的比较。于是稍加改进得到:voidget_nextval(StringT,intftnext)(i=l;j=0nextl=0;while(i=T.Length)if(J=OHTi=Tj)+il+j;if(Ti!=Tj)nexti=j;elsenexti=nextj;消去多余的可能的比较,next再向前跳elsej=nextj;)三、分析理论时间简单性这个程序或许比想像中的要简洁，由于对于i值的不断增加,代码用的是for循环。因此，这个代码可以这样形象地理解：扫描字符串S,并更新可以

7、匹配到T的什么位置。为什么这个程序是0(n)的？KMP的时间简单度分析可谓摊还分析的典型。我们从上述程序的j值入手。每一次执行While循环都会使j减小(但不能减成负的)，而此外的转变j值的地方只有第五行。每次执行了这一行，j都只能加1;因此，整个过程中j最多加了n个1。于是，j最多只有n次减小的机会(j值减小的次数当然不能超过n,由于j永久是非负整数)。这告知我们，While循环总共最多执行了n次。根据摊还分析的说法，平摊到每次for循环后，一次for循环的简单度为0(1)。整个过程明显是0(n)的。这样的分析对于后面P数组预处理的过程同样有效，同样可以得到预处理过程的简单度为0(m)。.四

8、、原程序和调试结果packagekmp;publicclasskmpStrings=aaaaaaaa;Stringp=aaaab;intnext=newints.length();主要计算next的值voidcalnet()(intizj=0;nextl=0;nextO=-l;for(i=2;is.length();i+)(if(s.charAt(j)=s.charAt(i-l)(nexti=nexti-l+l;j+;)else(if(nextjO)nexti=O;elsenexti=nextj;j=nexti;)输出实际运算次数voiddisplay)inti=OJ=O,v;intcount=0;while(is.length()&jp.length()(if(s.charAt(i)=p.charAt(j)(i+；j+；)elseif(j=O)i+;elsej=nextj;count+;)System.out.println(,+count);)publicstaticvoidmain(Stringargs)/TODOcodeapplicationlogicherekmpk=newkmp();k.calnext();k.display();五、对结果的分析进行了12次匹配，匹配胜利。