kmp算法详解

sdhzmmw 贡献于2012-12-24

作者 微软用户  创建于2010-12-07 09:37:00   修改者微软用户  修改于2010-12-07 09:38:00字数4241

文档摘要:首先在(a)中p1=s1,p2=s2,p3≠s3,只需将模式右移到s3,不需将主串回溯到s2; 其次,由于p1≠p2,可推出p1≠s2,做(b)的比较一定不等; 再由p1=p3,可以推出p1≠s3,做(c)的比较也一定不等。 因此,由(a)便可直接将P右移三位跳到(d),从p1和t4开始进行比较,这样的匹配过程对S(主串)而言就消除了回溯。
关键词:

(1)以一个例子引入KMP算法 先看朴素模式匹配过程: (a)S: a  b  b  a  b  a        =  =  ≠    P: a  b  a (b)P3≠S3,P右移一位    S: a  b  b  a  b  a       (c) P1≠S2,P右移一位     S: a  b  b  a  b  a               ≠     P:       a  b  a (d) P1≠S3,P右移一位    S: a  b  b  a  b  a                 =  =  =    P:          a  b  a (e)匹配成功index(S,P)=4,  substr(S,4,3)=P     从匹配过程看:     首先在(a)中p1=s1,p2=s2,p3≠s3,只需将模式右移到s3,不需将主串回溯到s2;     其次,由于p1≠p2,可推出p1≠s2,做(b)的比较一定不等; 再由p1=p3,可以推出p1≠s3,做(c)的比较也一定不等。     因此,由(a)便可直接将P右移三位跳到(d),从p1和t4开始进行比较,这样的匹配过程对S(主串)而言就消除了回溯。     为要找到一个无回溯的匹配算法,关键在于当匹配过程中,一旦pj和si比较不等,存在:   substr(p,1,j-1)=substr(s,i-j+1,j-1) pj≠si   改进的模式匹配算法的思想:    在匹配过程中,当主串第i个字符与模式串第j个字符“失配”时,要产生模式串右移的位数和继续与主串(主串无回溯的)比较的字符,即应该用P中哪个字符和Si进行比较?把这个字符记为Pk,显然有k0表示一旦匹配过程中Pi 与Si 比较不等,可用模式中next[j]为下标的字符与Si 进行比较;     若next[j]=0表示P中任何字符都不必再与Si 进行比较,而从Si+1开始 。     对于任何模式P,主要的是要确定next[j](j=1,2,3…m)值,next[j] 确定了,就可以加快匹配的过程。     当Pj ≠Si时,P直接右移j-next[j]个字符,或者说P从next[j]开始与Si 继续比较下去。   KMP算法:假设next[j]已经生成。 int index_KMP(strtype p,strtype s,int pos) {int i=pos,j=1;  while(j<=m&&i<=n)   //m是模式串p的串长,n是主串s的串长   {if(j==0||s.str[i]==p.str[j]);             {i++;j++;}    else j=next[j];   }  if(j>m) return i-m;  else return 0; }   (2)next[j]数组的性质 从上面的分析可以看出,此种算法的关键在于确定next[j]数组。 若令next[j]=k ,则有:  ①  1≤k

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档