kmp算法课件演示推荐Word文档格式.docx
- 文档编号:6818447
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:11
- 大小:18.26KB
kmp算法课件演示推荐Word文档格式.docx
《kmp算法课件演示推荐Word文档格式.docx》由会员分享,可在线阅读,更多相关《kmp算法课件演示推荐Word文档格式.docx(11页珍藏版)》请在冰点文库上搜索。
(d)P1≠S3,P右移一位
abbaba
===
aba
(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,显然有k<
j,并且对不同的j,k值也不相同。
这个k值仅依赖于模式P本身前j个字符的构成,而与目标S无关。
一般用next[j]表示与j对应的k值,表明当模式中第j个字符与主串中第i个字符“失配”时,在模式中需重新和主串中第i字符进行比较的字符的位置。
s1s2……………..si-k+1……..si-1sisi+1……sn
p1p2……pk-1pk.pj-k+1…………pj-1pjpj+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|1<
k<
j且“p1p2…pk-1”=“pj-k+1pj-k+2…pj-1”
1其它情况
例:
i=3
第一趟匹配ababcabcacbab
abcac
j=3next[3]=1
i—i=7
第二趟匹配ababcabcacbab
—j=5next[5]=2
j=1
i—i=10
第三趟匹配ababcabcacbab
j=2
其意义在于:
若next[j]>
0表示一旦匹配过程中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]已经生成。
intindex_KMP(strtypep,strtypes,intpos)
{inti=pos,j=1;
while(j<
=m&
&
i<
=n)//m是模式串p的串长,n是主串s的串长
{if(j==0||s.str[i]==p.str[j]);
{i++;
j++;
}
elsej=next[j];
}
if(j>
m)returni-m;
elsereturn0;
(2)next[j]数组的性质
从上面的分析可以看出,此种算法的关键在于确定next[j]数组。
若令next[j]=k,则有:
①
1≤k<
j
②substr(P,1,k-1)=substr(P,j-k+1,k-1)
性质②说明,若存在这样的k(next[j]),就应有P的前缀子串k-1个字符与后缀子串k-1个字符相等。
由性质②可以看出next数组只与模式P本身有关,而与主串S无关。
因此对给定的模式P,我们可以在进行模式匹配之前预先求出next数组的值。
(3)next[j]数组的生成
由性质可知,next[j]的值就等于这个串p1p2pj-1中相同的前缀子串和后缀子串的最大长度加1。
找前缀和后缀相同的最大真子串,实质上仍然是一个模式匹配,只是匹配的模式串和目标串是同一个串P。
由定义知:
a.next[1]=0
设next[j]=k
b.若pk=pj时,则next[j+1]=next[j]+1
c.若pk≠pj,则next[j+1]=next[k]+1
d.若不存在匹配的子串:
next[j+1]=1
j:
12345678
p:
abaabcac
k:
01122312
p3=p1Next[4]=next[3]+1=2
p4≠p2
p4=p1next[5]=next[2]+1=1+1=2
P5=p2Next[6]=next[5]+1=3
p6
≠p3
≠p1next[7]=1
p7=p1
next[8]=next[7]+1=2
next函数的算法:
求next数组
voidnext(strtypet)
{intnext[m],j=1,k=0;
next[1]=0;
t.len)
{if(k=0||t.str[j]==t.str[k])
{j++;
k++;
next[j]=k;
elsek=next[k];
//向前递推找最大匹配的k,模式串右移
方法归纳如下:
a.考察模式串,令next[1]=0;
b.对于从第2个字符开始的next[j],分析在j位置前的j-1个字符串中是否存在一个k,使得在k前的k-1个子串等于j前的k-1个子串(即j前的j-1个字符存在前后缀子串匹配);
若不存在,则next[j]=1;
存在,则next[j]=k。
注意:
k应使匹配子串最大。
已知模式串p=‘abcaabbabcab’,写出用KMP法求得的
每个字符对应的next和nextval函数值。
序号j:
123456789101112
模式p:
abcaabbabcab
next[j]:
011122312345
nextval[j]:
011021101105
(4)next函数修正值算法
分析模式“aaaab”的next[j]。
序号j:
12345
模式:
aaaab
next[j]:
01234
目标串:
aaabaaaab
模式串:
j=next[4]=3aaaab
j=next[3]=2aaaab
j=next[2]=1aaaab
j=next[1]=0aaaab
匹配成功
若对于next[j]=k,有pj=pk,当主串中的字符ti和pj比较不等时,不需要再和pk进行比较,而直接和pnext[k]进行比较,也就是说,此时,next[j]=next[k]。
序号j:
nextval[j]:
00004
j=nextval[4]=0aaaab
从而得出新的next数组——修正函数nextval的算法。
voidnextval(strtypet)
{intnextval[m],i=1,j=0;
nextval[1]=0;
while(i<
{if(j=0||t.str[i]==t.str[j])
if(t.str[i]!
=t.str[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
elsej=nextval[j];
(5)举例
设一模式串为p=’abcaababc’(m=9)
目标串为t=’aabcbabcaabcaababc’(n=18)
要求手工计算next数组和nextval数组;
并进行模式匹配,确定模式串在目标串中位置。
①手工计算next数组和nextval数组的值为:
序号j123456789
模式串abcaababc
next[j]011122323
nextval[j]011021311
a.计算next数组:
next[1]=0。
next[2]=1,next[2]前不存在p1…pk-1=pi-k+1…pi-1,因b前只有一个a;
next[3]=1,同理,c前只有ab。
next[4]=1,同上道理。
next[5]=2,因为在j位置上a前有p1=p4,即p2-1=p5-2+1因此,k=2,即next[5]=2。
next[6]=2,道理同next[5]。
next[7]=3,因为在j位置上a前有p1p2=p5p6,即
p1p3-1=p7-3+1p7-1,因此,k=3,即next[7]=3。
next[8]=2,道理同j为5,6。
next[9]=3,道理同j为7。
b.计算nextval数组:
nextval[1]=0。
nextval[2]=1,nextval[3]=1,同上。
nextval[4]=0,next[4]=1,因为p4=p1=a,所以,nextval[4]=nextval[1]=0。
nextval[5]=2,因为next[5]=2,但pj≠pk,所以,nextval[5]=next[5]=2。
nextval[6]=1,因为next[6]=2,而p6=p2,所以,nextval[6]=next[2]=1。
nextval[7]=3,因为next[7]=3,但p7≠p3,所以,nextval[7]=next[7]=3。
nextval[8]=1,因为next[8]=2,而p8=p2,所以,nextval[8]=next[2]=1。
nextval[9]=1,因为next[9]=3,而p9=p3,所以,nextval[9]=next[3]=1。
②模式匹配确定模式串在目标串中的位置
序号j:
123456789101112131415161718
目标T:
aabcbabcaabcaababc
模式P:
abcaababc
j=next[2]=1
abcaababc
j=next[4]=1
j=next[1]=0
j=next[7]=3
aabcbabcaabcaababc
j=nextval[2]=1
j=nextval[4]=0
j=nextval[7]=3
a
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- kmp 算法 课件 演示 推荐