数据结构串的模式匹配本.ppt

《数据结构串的模式匹配本.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），若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]则需往前回溯，检