kmp算法课件演示(推荐)

《kmp算法课件演示(推荐)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、kmp算法课件演示(推荐)数据结构/数据库2007-10-1222:23:51阅读625评论1  字号：大中小 订阅(1)以一个例子引入KMP算法先看朴素模式匹配过程：(a)S：abbaba==≠P：aba012(b)P3≠S3,P右移一位S：abbaba(c)P1≠S2,P右移一位S：abbaba≠P：aba(d)P1≠S3,P右移一位S：abbaba===P：aba(e)匹配成功index(S,P)=4,substr(S,4,3)=P  从匹配过程看：首先在(a)中p1=s1,p2=s2,p3≠s3,只需将

2、模式右移到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

3、个字符“失配”时，要产生模式串右移的位数和继续与主串（主串无回溯的）比较的字符，即应该用P中哪个字符和Si进行比较？把这个字符记为Pk，显然有k

4、j+1…..pm假设此时应与模式串中第k个字符继续比较，则模式中前k-1个字符的子串必须满足下列关系：“p1p2…pk-1”=“si-k+1si-k+2…si-1”由部分匹配知：“pj-k+1pj-k+2…pj-1”=“si-k+1si-k+2…si-1”推得：“p1p2…pk-1”=“pj-k+1pj-k+2…pj-1                 0当j=1时 next[j]= Max{k

5、1

6、c01112 例：¯i=3第一趟匹配ababcabcacbababcacj=3next[3]=1¯i—®¯i=7第二趟匹配ababcabcacbababcac—®j=5next[5]=2j=1¯i—®¯i=10第三趟匹配ababcabcacbababcacj=2 其意义在于：若next[j]>0表示一旦匹配过程中Pi与Si比较不等，可用模式中next[j]为下标的字符与Si进行比较；若next[j]=0表示P中任何字符都不必再与Si进行比较，而从Si+1开始。对于任何模式P，主要的是要确定next[j](j=1

7、,2,3…m)值，next[j]确定了，就可以加快匹配的过程。当Pj≠Si时，P直接右移j-next[j]个字符，或者说P从next[j]开始与Si继续比较下去。 KMP算法：假设next[j]已经生成。intindex_KMP(strtypep,strtypes,intpos){inti=pos,j=1;while(j<=m&&i<=n)//m是模式串p的串长，n是主串s的串长{if(j==0

8、

9、s.str[i]==p.str[j]);{i++;j++;}elsej=next[j];}if(j>m)retur

10、ni-m;elsereturn0;} (2)next[j]数组的性质从上面的分析可以看出，此种算法的关键在于确定next[j]数组。若令next[j]=k,则有： ① 1≤k

11、的生成由性质可知，next[j]的值就等于这个串p1p2pj-1中相同的前缀子串和后缀子串的最大长度加1。找前缀和后缀相同的最大真子串，实质上仍然是一个模式匹配，只是匹配的模式串和目标串是同一个串P。由定义知：a.next[1]=0设next[j]=kb.若pk=pj时，则next[j+1]=next[j]+1c.若pk≠pj，则next[j+1]=next[k]+1d.若不存在匹配的