欢迎来到天天文库
浏览记录
ID:51157908
大小:375.00 KB
页数:19页
时间:2020-03-19
《数据结构串的模式匹配本.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第四章串的模式匹配算法本讲内容4.3串的模式匹配算法1.朴素的模式匹配算法2.KMP算法1.模式串的next和nextval函数值2.手工模拟KMP算法的执行过程采用串的定长顺序存储结构,讨论不依赖于其他串操作的模式匹配算法(子串定位操作)。朴素的模式匹配算法Index(S,T,pos)算法思想从主串S的第pos个字符起和模式T的第一个字符比较,若相等,则继续逐个比较后续字符;否则,从主串的下一个字符起再重新和模式T的字符比较。依次类推,直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等,则称
2、匹配成功,否则称匹配失败。匹配成功时,返回和模式T中第一个字符相等的字符在主串S中的位置;匹配失败时,返回零。朴素的模式匹配算法S串posiT串jijijijijT串朴素的模式匹配主串S=’ababcabcacbab’,模式串T=’abcac’,pos=1↓i=3第一趟匹配:ababcabcacbababc↑j=3↓i=2第二趟匹配:ababcabcacbaba↑j=1↓i=7第三趟匹配:ababcabcacbababcac↑j=5第四趟匹配:ababcabcacbaba↑j=1↓i=5第五趟匹配:aba
3、bcabcacbaba↑j=1↓i=11第六趟匹配:ababcabcacbababcac(成功)↑j=6↓i=4intIndex(SStringS,SStringT,intpos){//返回子串T在主串S中第pos个字符之后的位置。若不存在,//则函数值为0。其中,T非空,1≤pos≤StrLength(S)。i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}//继续比较后继字符else{i=j=1;}//指针后退重新开始匹配}if(j>T
4、[0])returni-T[0];elsereturn0;}//Indexi-j+2;算法分析2.算法最坏情况下的时间复杂度为O(n*m)1.如果主串中可能存在多个和模式串“部分匹配”的子串,因而引起主串中指针i的多次回溯。上面的模式匹配只需三趟主串S=’ababcabcacbab’,模式串T=’abcac’↓i=3第一趟匹配:ababcabcacbababc↑j=3(next[3]=1)↓i=3第二趟匹配:ababcabcacbababcac↑j=5(next[5]=2)↓i=7第三趟匹配:ababca
5、bcacbab(a)bcac↑j=2怎么得来的呢?这就是KMP算法。KMP算法KMP—Knuth,Morris,Pratt三人发明特点:无需回溯;在O(n+m)的时间量级上完成串的模式匹配操作;KMP算法假设主串S为’s1s2s3…sn’,模式串T为’p1p2…pm’,若si与pj发生失配,则有:’si-j+1…si-1’=’p1…pj-1’(1)由(1),若k6、i-k+1…si-1’=’p1…pk-1’(2)由(2)和(3),则下式成立:’p1…pk-1’==’pj-k+1…pj-1’(4)该等式只与模式串有关,与主串无关。KMP算法模式串的next函数定义若模式串P为’abaabc’,由定义可得next函数值:j123456模式串abaabcnext[j]011223↓i=2第一趟匹配:主串acabaabaabcacaabc模式串ab↑j=2next[2]=1↓i=2第二趟匹配:主串acabaabaabcacaabc模式串a↑j=1next[1]=0↓i=3→7、↓i=8第三趟匹配:主串acabaabaabcacaabc模式串abaabc↑j=1→↑j=6next[6]=3↓i=8→↓i=12第四趟匹配:主串acabaabaabcacaabc模式串(ab)aabc↑j=3→↑j=7KMP算法手工模拟主串S=’acabaabaabcacaabc’模式串T=’abaabc’intIndex_KMP(SStringS,SStringT,intpos){//1≤pos≤StrLength(S)i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(j==8、09、10、S[i]==T[j]){++i;++j;}//继续比较后继字符elsej=next[j];//模式串向右移动}if(j>T[0])returni-T[0];//匹配成功elsereturn0;}//Index_KMP不存在这样的k,则next[j+1]=1求next函数值的过程是一个递推过程,分析如下:已知:next[1]=0;假设:next[j]=k;则:next[j+1]=k+1若:T[j]T[k]则需往前回溯,检
6、i-k+1…si-1’=’p1…pk-1’(2)由(2)和(3),则下式成立:’p1…pk-1’==’pj-k+1…pj-1’(4)该等式只与模式串有关,与主串无关。KMP算法模式串的next函数定义若模式串P为’abaabc’,由定义可得next函数值:j123456模式串abaabcnext[j]011223↓i=2第一趟匹配:主串acabaabaabcacaabc模式串ab↑j=2next[2]=1↓i=2第二趟匹配:主串acabaabaabcacaabc模式串a↑j=1next[1]=0↓i=3→
7、↓i=8第三趟匹配:主串acabaabaabcacaabc模式串abaabc↑j=1→↑j=6next[6]=3↓i=8→↓i=12第四趟匹配:主串acabaabaabcacaabc模式串(ab)aabc↑j=3→↑j=7KMP算法手工模拟主串S=’acabaabaabcacaabc’模式串T=’abaabc’intIndex_KMP(SStringS,SStringT,intpos){//1≤pos≤StrLength(S)i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(j==
8、0
9、
10、S[i]==T[j]){++i;++j;}//继续比较后继字符elsej=next[j];//模式串向右移动}if(j>T[0])returni-T[0];//匹配成功elsereturn0;}//Index_KMP不存在这样的k,则next[j+1]=1求next函数值的过程是一个递推过程,分析如下:已知:next[1]=0;假设:next[j]=k;则:next[j+1]=k+1若:T[j]T[k]则需往前回溯,检
此文档下载收益归作者所有