欢迎来到天天文库
浏览记录
ID:18363315
大小:88.00 KB
页数:13页
时间:2018-09-16
《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,显然有k4、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{k5、16、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=17、,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==08、9、s.str[i]==p.str[j]);{i++;j++;}elsej=next[j];}if(j>m)retur10、ni-m;elsereturn0;} (2)next[j]数组的性质从上面的分析可以看出,此种算法的关键在于确定next[j]数组。若令next[j]=k,则有: ① 1≤k11、的生成由性质可知,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.若不存在匹配的
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、16、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=17、,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==08、9、s.str[i]==p.str[j]);{i++;j++;}elsej=next[j];}if(j>m)retur10、ni-m;elsereturn0;} (2)next[j]数组的性质从上面的分析可以看出,此种算法的关键在于确定next[j]数组。若令next[j]=k,则有: ① 1≤k11、的生成由性质可知,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.若不存在匹配的
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≤k11、的生成由性质可知,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.若不存在匹配的
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.若不存在匹配的
此文档下载收益归作者所有