数据结构串的模式匹配本.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第一趟匹配：ababcabcacbababcj=3i=2第二趟匹配：ababcabcacbabaj=1i=7第三趟匹配：ababcabcacbababcacj=5,第四趟匹配：ababcabcacbabaj=1i=5第五趟匹配：ababcabcacbabaj=1i=11第六趟匹配：ababcabcacbababcac（成功）j=6,i=4,intIndex(SStringS,SStringT,intpos)/返回子串T在主串S中第pos个字符之后的位置。若不存在，/则函数值为0。其中，T非空，1posStrLength(S)。i=pos;j=1;while(iT0)returni-T0;elsereturn0;/Index,i-j+2;,算法分析,2.算法最坏情况下的时间复杂度为O(n*m),1.如果主串中可能存在多个和模式串“部分匹配”的子串，因而引起主串中指针i的多次回溯。,上面的模式匹配只需三趟,主串S=ababcabcacbab，模式串T=abcac,i=3第一趟匹配：ababcabcacbababcj=3(next3=1)i=3第二趟匹配：ababcabcacbababcacj=5(next5=2)i=7第三趟匹配：ababcabcacbab(a)bcacj=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第一趟匹配：主串acabaabaabcacaabc模式串abj=2next2=1i=2第二趟匹配：主串acabaabaabcacaabc模式串aj=1next1=0i=3i=8第三趟匹配：主串acabaabaabcacaabc模式串abaabcj=1j=6next6=3i=8i=12第四趟匹配：主串acabaabaabcacaabc模式串(ab)aabcj=3j=7,KMP算法手工模拟,主串S=acabaabaabcacaabc模式串T=abaabc,intIndex_KMP(SStringS,SStringT,intpos)/1posStrLength(S)i=pos;j=1;while(iT0)returni-T0;/匹配成功elsereturn0;/Index_KMP,不存在这样的k，则nextj+1=1,求next函数值的过程是一个递推过程，分析如下:,已知：next1=0；,假设：nextj=k；,则：nextj+1=k+1,若：TjTk则需往前回溯，检查Tj=T？,又Tj=Tk,k=nextj,即：nextj+1=nextj+1,k,即：nextj+1=nextk+1,01122343,求模式串的next函数值举例,这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串,voidget_next(SString/get_next,next函数的改进,当i4、j4时sipj，由nextj的指示还需进行i4、j3，i4、j2，i4、j1等三次比较。实际上，由于模式中第1、2、3个字符和第4个字符都相等，因此这种比较是不必要的，可以将模式串一次向右滑动4个字符直接进行i5、j1的比较。也就是说，若nextj