串的模式匹配ppt课件.ppt

《串的模式匹配ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、串的模式匹配算法雅礼朱全民串的基本操作串的连接（concat）求子串（substr---Pascal中的copy函数）插入函数（insert）删除函数（delete）定位函数（index---Pascal中的pos函数）模式匹配算法模式匹配基本思想：从主串s的第一个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后序字符，否则从主串的第二个字符起再重新和模式的字符比较之。依次类推，直至模式t中的每个字符依次和主串s中的一个连续字符序列相等，则称匹配成功，否则匹配不成功。算法框架FUNCpos(p,s:string):integer;{求模式串t在主串s中的位置的

2、定位函数}i:=1;j:=1{指针初始化}WHILE(i<=length(s))and(j<=length(p)DOIFs[i]=p[j]THEN[i:=i+1;j:=j+1]{继续比较后续字符}ELSE[i:=i-j+2;j:=1];{指针后退重新匹配}IFj>length(p)THENRETURN(i–length(p))ELSERETURN(0)ENDF;复杂性分析:最坏情况为O(n*m)例如:模式串为‘00000001’主串为:‘0000000000000000000000000000000000000000000000000000000000001’KMP(

3、Knuth-Morris-Pratt)算法KMP的基本原理由(1)可知,pj-k+1pj-k+2…pj-1=si-k+1si-k+2…si-1--------(1)由(2)可知,p1p2…pk-1=si-k+1si-k+2…si-1--------(2)所以有p1p2…pk-1=pj-k+1pj-k+2…pj-1--------(3)怎样求KKMP示例KMP算法框架FUNCKMP(p,t:string):integer;i:=1;j:=1{指针初始化}WHILE(i<=length(s))and(j<=length(p)DOIFs[i]=p[j]THEN[i:=i+1

4、;j:=j+1]{继续比较后续字符}ELSEj:=next[j];{模式串向右滑动next[j]}IFj>length(p)THENRETURN(i–length(p))ELSERETURN(0)ENDF;怎样求next[j]?首先有,next[1]=0,设next[j]=k,表明:p1p2…pk-1=pj-k+1pj-k+2…pj-1(1)若pk=pj,则在模式串中有,p1p2…pk=pj-k+1pj-k+2…pj所以,next[j+1]=k+1(2)若pk<>pj,则杂模式串中有p1p2…pk<>pj-k+1pj-k+2…pj则可将求next函数的问题看成整个模式

5、串既是主串又是模式串的问题,应将模式串滑动到next[k]个字符和主串的第j个字符相比较.若next[k]=k’,且pj=pk’,则说明在主串中第j+1个字符之前存在一个长度为k’的最长子串,和模式串中从首字符起长度为k’的子串相等,即p1p2…pk’<>pj-k’+1pj-k+2…pj也就是说next[j+1]=k’+1=next[k]+1求NEXT算法Procget_next(t:string);{next为全程变量}j:=1;k:=0;next[1]:=0;Whilej

6、k+1;next[j]:=k]elsek:=next[k]ENDP该算法的时间复杂度仅为O(length(p))扩展KMP算法给定母串S，和子串T。定义n=

7、S

8、,m=

9、T

10、，extend[i]=S[i..n]与T的最长公共前缀长度。请在线性的时间复杂度内，求出所有的extend[1..n]。容易发现，如果有某个位置i满足extend[i]=m，那么T就肯定在S中出现过，并且进一步知道出现首位置是i——而这正是经典的KMP问题。因此可见“扩展的KMP问题”是对经典KMP问题的一个扩充和加难。一个例子这里为了计算extend[1]，我们进行了11次比较运算aaaaaaa

11、aaabaaaaaaaaaaaaaa红色箭头表示失配在第11个位置失配aaaaaaaaaabaaaaaaaaaaaaaa红色箭头表示失配在第11个位置失配extend[2]=9。为了计算extend[2]，我们是不是也要进行10次比较运算呢？分析不然。因为通过计算extend[1]=10，我们可以得到这样的信息：S[1..10]=T[1..10]S[2..10]=T[2..10]。计算extend[2]的时候，实际上是S[2]开始匹配T。因为S[2..10]=T[2..10]，所以在匹配的开头阶段是“以T[2..10]为母串，T为子串”的匹配。不妨