数据结构串的模式匹配本.ppt
第四章 串的模式匹配算法,本讲内容,4.3 串的模式匹配算法,1.朴素的模式匹配算法,2.KMP算法,1.模式串的next和nextval函数值 2.手工模拟KMP算法的执行过程,采用串的定长顺序存储结构，讨论不依赖于其他串操作的模式匹配算法（子串定位操作）。,朴素的模式匹配算法,Index(S,T,pos)算法思想,从主串S的第pos个字符起和模式T的第一个字符比较，若相等，则继续逐个比较后续字符；否则，从主串的下一个字符起再重新和模式T的字符比较。依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，否则称匹配失败。匹配成功时，返回和模式T中第一个字符相等的字符在主串S中的位置；匹配失败时，返回零。,朴素的模式匹配算法,S 串,pos,i,T 串,j,i,j,i,j,i,j,i,j,T 串,朴素的模式匹配,主串 S=ababcabcacbab，模式串T=abcac，pos=1,i=3第一趟匹配：a b a b c a b c a c b a b a b c j=3 i=2第二趟匹配：a b a b c a b c a c b a b a j=1 i=7 第三趟匹配：a b a b c a b c a c b a b a b c a c j=5,第四趟匹配：a b a b c a b c a c b a b a j=1 i=5 第五趟匹配：a b a b c a b c a c b a b a j=1 i=11 第六趟匹配：a b a b c a b c a c b a b a b c a c（成功）j=6,i=4,int Index(SString S,SString T,int pos)/返回子串T在主串S中第pos个字符之后的位置。若不存在，/则函数值为0。其中，T非空，1posStrLength(S)。i=pos;j=1;while(i T0)return i-T0;else return 0;/Index,i-j+2;,算法分析,2.算法最坏情况下的时间复杂度为O(n*m),1.如果主串中可能存在多个和模式串“部分匹配”的子串，因而引起主串中指针i的多次回溯。,上面的模式匹配只需三趟,主串S=ababcabcacbab，模式串T=abcac,i=3第一趟匹配：a b a b c a b c a c b a b a b c j=3(next3=1)i=3第二趟匹配：a b a b c a b c a c b a b a b c a c j=5(next5=2)i=7 第三趟匹配：a b a b c a b c a c b a b(a)b c a c j=2 怎么得来的呢？这就是KMP算法。,KMP算法,KMPKnuth,Morris,Pratt三人发明,特点：无需回溯；在O(nm)的时间量级上完成串的模式匹配操作；,KMP算法,假设主串S为s1s2s3sn，模式串T为p1p2pm，若si与pj发生失配，则有：si-j+1si-1=p1pj-1(1),由（1），若kj,则有：si-k+1si-1=pj-k+1pj-1(3),若主串不回溯，设此时将与模式串中第k（kj）个字符继续比较，则有：si-k+1si-1=p1pk-1(2),由（2）和（3），则下式成立：p1pk-1=pj-k+1pj-1（4）该等式只与模式串有关，与主串无关。,KMP算法,模式串的next函数定义,若模式串P为 abaabc，由定义可得next函数值：,i=2第一趟匹配：主串 a c a b a a b a a b c a c a a b c 模式串 a b j=2 next2=1 i=2第二趟匹配：主串 a c a b a a b a a b c a c a a b c 模式串 a j=1 next1=0 i=3 i=8第三趟匹配：主串 a c a b a a b a a b c a c a a b c 模式串 a b a a b c j=1 j=6 next6=3 i=8 i=12第四趟匹配：主串 a c a b a a b a a b c a c a a b c 模式串(a b)a a b c j=3 j=7,KMP算法手工模拟,主串 S=a c a b a a b a a b c a c a a b c模式串 T=a b a a b c,int Index_KMP(SString S,SString T,int pos)/1posStrLength(S)i=pos;j=1;while(i T0)return i-T0;/匹配成功 else return 0;/Index_KMP,不存在这样的k，则nextj+1=1,求next函数值的过程是一个递推过程，分析如下:,已知：next1=0；,假设：nextj=k；,则：nextj+1=k+1,若：Tj Tk则需往前回溯，检查Tj=T？,又 Tj=Tk,k=nextj,即：nextj+1=nextj+1,k,即：nextj+1=nextk+1,0 1 1 2 2 3 4 3,求模式串的next函数值举例,这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串,void get_next(SString/get_next,next函数的改进,当i4、j4时sipj，由nextj的指示还需进行i4、j3，i4、j2，i4、j1等三次比较。实际上，由于模式中第1、2、3个字符和第4个字符都相等，因此这种比较是不必要的，可以将模式串一次向右滑动4个字符直接进行i5、j1的比较。也就是说，若nextj=k，当si与pj失配且pjpk，则下一步不需将主串中的si与pk比较，而是直接与nextk进行比较。,主串a a a b a a a a b,a a a a b,void get_nextval(SString/get_nextval,
