模式匹配的KMP算法详解_第1页
模式匹配的KMP算法详解_第2页
模式匹配的KMP算法详解_第3页
模式匹配的KMP算法详解_第4页
全文预览已结束

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、模式匹配的KMP 算法详解模式匹配的KMPT法详解这种由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 同时发现的改进的模式匹配算法简称为KMPJ法。大概学过信息学的都知道,是个比较难理解的算法,今天特把它搞个彻彻底底明明白白。注意到这是一个改进的算法,所以有必要把原来的模式匹配算法拿出来,其实理解的关键就在这里,一般的匹配算法:int Index(String S,String T,int pos)/参考数据结构中的程序i=pos;j=1;/ 这里的串的第1 个元素下标是1while(i<=S.Length && j<=T.Length)if(

2、Si=Tj)+i;+j;elsei=i-j+2;j=1;/*(1)if(j>T.Length) return i-T.Length;/匹配成功else return 0;匹配的过程非常清晰,关键是当失配的时候程序是如何处理的?回溯,没错,注意到(1) 句,为什么要回溯,看下面的例子:S:aaaaabababcaaa T:ababcaaaaabababcaaaababc.(. 表示前一个已经失配)回溯的结果就是aaaaabababcaaaa.(babc)如果不回溯就是aaaaabababcaaaaba.bc这样就漏了一个可能匹配成功的情况aaaaabababcaaaababc为什么会发生这

3、样的情况?这是由T用本身的性质决定的,是因为T申本身有前后部分匹配的性质。如果T为abcdef这样的,大没有回溯的必要。改进的地方也就是这里,我们从 T用本身出发,事先就找准了 T自身前后部分 匹配的位置,那就可以改进算法。如果不用回溯,那T用下一个位置从哪里开始呢?还是上面那个例子,T为ababc,如果c失配,那就可以往前移到 aba最后一个 a 的位置,像这样:.ababd. ababc ->ababc这样i不用回溯,j跳到前2个位置,继续匹配的过程,这就是 KMPJ法所在 这个当Tj失配后,j应该往前跳的值就是j的next值,它是由T用本身固 有决定的,与S用无关。数据结构上给了n

4、ext 值的定义:0如果j=1nextj=Maxk|1<k<j 且 'p1.pk-1'='pj-k+1.pj-1'1其它情况我当初看到这个头就晕了,其实它就是描述的我前面表述的情况,关于 next1=0 是规定的,这样规定可以使程序简单一些,如果非要定为其它的值只要不和后面的值冲突也是可以的;而那个Max是什么意思,举个例子:T:aaab.aaaab. aaab->aaab->aaab->aaab像这样的T,前面自身部分匹配的部分不止两个,那应该往前跳到第几个呢?最近的一个,也就是说尽可能的向右滑移最短的长度。OK 了解到这里,就看

5、清了 KMP勺大部分内容,然后关键的问题是如何求next 值?先不管它,先看如何用它来进行匹配操作,也就是说先假设已经有了next 值。将最前面的程序改写成:int Index_KMP(String S,String T,int pos)i=pos;j=1;/ 这里的串的第1 个元素下标是1while(i<=S.Length && j<=T.Length)if(j=0 | Si=Tj)+i;+j; /注意到这里的j=0, 和 +j 的作用就知道为什么规定next1=0 的好处了else j=nextj;/i不变(不回溯),j 跳动if(j>T.Length)

6、return i-T.Length;/匹配成功else return 0;OK,是不是非常简单?还有更简单的,求next值,这也是整个算法成功的关键,从 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=

7、j;/*(2)*/ else j=nextj;看这个函数是不是非常像 KMPS配的函数,没错,它就是这么干的!注意到(2)语句逻辑覆盖的时候是Ti=Tj 以及 i 前面的、 j 前面的都匹配的情况下,于是先自增,然后记下来nexti=j , 这样每当i 有自增就会求得一个nexti ,而j 一定会小于等于i ,于是对于已经求出来的next,可以继续求后面的nex t ,而 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;/消去

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论