字符串匹配算法：穷举、KMP、BM

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 字符串,字符串,(,String,),字符串是,n(,0),个字符的有限序列，记作,S:“,c,0,c,1,c,2,c,n-1,”,其中，,S,是串名字,“,c,0,c,1,c,2,c,n-1,”,是串值,c,i,是串中字符,n,是串的长度。,如：“,Welcome to Shanghai!”,在计算机非数值计算应用中，经常遇到字符序列的处理。如，文字编辑、情报检索、自然语言翻译、事务处理、图象处理等应用中经常遇到的那样。在计算机中，一个字符集上的每个字符用定长的代码表示，所有可能的各种字符都可以对应一个确定的代码。一个特定的字符序列称为字符串，简称为串。有两种方法能比较方便地表示一个字符串。一是人为地约定一个特殊的代码为字符序列的结束符，每个字符串最后都有这个结束符。二是，为每个字符序列另引入一个整数，让该整数指出该字符串的字符个数。本书采用第一种表示字符串的方法,模式匹配是串的基本运算之一。,有两个字符串,T,和，字符串,T,称为正文，字符串,S,称为模式，要求找出模式,S,在正文,T,中的首次出现的位置。一旦模式,S,在正文,T,中找到，就说发生一次匹配。有些应用可能会要求找出所有的匹配位置。,串的模式匹配,定义,在串中寻找子串（第一个字符）在串中的位置,词汇,在模式匹配中，子串称为,模式,，串称为,目标,。,示例,目标,T:,“,Beijing,”,模式,P:,“,jin,”,匹配结果,=3,记正文,T,的字符个数为,n,，令,T=t,0,t,1,t,2,t,n-1,，,记模式,S,的字符个数为,m,，令,S=s,0,s,1,s,2,s,m-1,。,若正文中自位置,k,开始有一次匹配，则有,s,j,=t,k+j,，,0=j m,。,并且对所有,pk,，没有对所有的,0=jm,，,m,个等式,s,j,=t,p+j,全都成立。,7.1,简单匹配,第,1,趟,T,a b b a b a,穷举的模式,P,a b a,匹配过程,第,2,趟,T,a b b a b a,P,a b a,第,3,趟,T,a b b a b a,P,a b a,第,4,趟,T,a b b a b a,P,a b a,char*stringSearch(char*t,char*p),int n=strlen(t),m=strlen(p),i,j;,for(j=0;j=n-m;j+),/*,从,tj,开始的子串与字符串,p,比较*,/,for(i=0;i m,if(i=m)return t+j;,return NULL;,若不考虑正文至少有模式长的字串个数，且用字符指针编写，可简写成以下形式。,char*stringSearch(char*t,char*s),char*q,*p;,for(;*t!=0;t+),for(q=t,p=s;*p!=0,q+,p+),return*p=0?t:NULL;,目标,T,S T U D E N S T U D E N T,模式,pat,S T U D E N T,目标,T,S T U D E,N S T U D E N T,模式,pat,S T U D E N T,目标,T,S T U D E,N S T U D E N T,模式,pat,S T U D E N T,简单模式匹配的缺点,:,无谓比较,目标,T,F I F I F I Y U D E N T,模式,pat,F I F I Y,目标,T,F I F I F I Y U D E N T,模式,pat,F I F I Y,直接跳过错过成功比较,目标,T,F I F I F I Y U D E N T,模式,pat,F I F I Y,直接跳过子串可能错过成功比较,穷举的模式匹配算法时间代价：,最坏情况比较,n,-,m,+1,趟，每,趟比较,m,次，,总比较次数达,(,n-m+,1)*,m,原因在于,每趟重新比较时，目标串的检,测指针要回退。改进的模式匹配算法可,使目标串的检测指针每趟不回退。,改进的模式匹配,(KMP),算法的时间代价：,若每趟第一个不匹配，比较,n,-,m,+1,趟，,总比较次数最坏达,(,n-m,)+,m=n,若每趟第,m,个不匹配，总比较次数最坏亦达到,n,7.2 KMP,算法,目标,T,t,0,t,1,t,2,t,j,-1,t,j,t,n,-1,X,模式,pat,p,0,p,1,p,2,p,j,-1,p,j,p,m,-1,目标,T,t,0,t,1,t,k,t,n,-1,模式,pat,p,0,p,1,p,m,-2,p,m,-1,改进的模式匹配：,寻找最大“跳跃”,T,t,0,t,s,-1,t,s,t,s,+1,t,s,+2,t,s+j,-,1,t,s+j,t,s+j,+1,t,n,-1,P,p,0,p,1,p,2,p,j,-,1,p,j,p,j,+1,则有,t,s,t,s,+1,t,s,+2,t,s+j,=,p,0,p,1,p,2,p,j,(1),为使模式,P,与目标,T,匹配，必须满足,p,0,p,1,p,2,p,j,-1,p,m,-1,=,t,s,+1,t,s,+2,t,s,+3,t,s+j,t,s+m,如果,p,0,p,1,p,j,-1,p,1,p,2,p,j,(2),则立刻可以断定,p,0,p,1,p,j,-1,t,s,+1,t,s,+2,t,s+j,下一趟必不匹配,同样，若,p,0,p,1,p,j,-2,p,2,p,3,p,j,则再下一趟也不匹配，因为有,p,0,p,1,p,j-,2,t,s,+2,t,s,+3,t,s+j,直到对于某一个“,k,”,值，使得,p,0,p,1,p,k,+1,p,j-k,-1,p,j-k,p,j,且,p,0,p,1,p,k,=,p,j-k,p,j-k,+1,p,j,则,p,0,p,1,p,k,=,t,s+j-k,t,s+j-k,+1,t,s+j,p,j-k,p,j-k,+1,p,j,因此，当正文,T,在,tj+i,比较失败时，正文,t,的扫视指针,j,不回溯，仍指向上一趟匹配失败的字符，即从此处开始继续比较，而模式,s,扫视指针,i,回退到,k,，即模式从,sk,开始，这就省去了前面的,k,次比较。如果对应,si,的,k,有多个，应取最大的,k,。,这样，在匹配比较过程中，一旦出现,si tj+i,时，就要找出,si,对应的,k,，称,k,为,si,的失败链接值。寻找,s,的各字符的失败链接值，只与模式,S,本身有关，与正文,T,无关。,设模式,S=s,0,s,1,s,m-1,，则它各字符的失败链接值,nextj,的定义如下：,k,，,当,0 s k j,，且使得,s,0,s,1,s,k,=,s,j-k,s,j-k+1,s,j,的最大整数,nextj=,-1,，其它情况,称,s,0,s,1,s,k,为,s,0,s,1,s,j-1,s,j,的前缀子串，,s,j-k,s,j-k+1,s,j,为,s,0,s,1,s,j-1,s,j,的后缀子串。,设模式,S=“xyxxyzxz”,，按上述公式求得各字符的失败链接值如表,7.1,所示。,表,7.1,字符失败链接值,J 0 1 2 3 4 5 6 7,S x y x x y Z x z,nextj -1 -1 0 0 1 -1 0 -1,j=0,时，没有满足,0skj,的,k,存在，,next0=-1,。,j=1,时，可取,k=0,，但,s0s1,，,k,不符合要求，,next1=-1,。,j=2,时，,k,可能取,0,或,1,，,s0=s2,，且,s0s1s1s2,，所以，,k=0,，,next2=0,。,j=3,时，,k,可能取,0,、,1,或,2,，,s0=s3,，且,s0s1s2s3,，,s0s1s2s1s2s3,，所以取,k=0,，,next3=0,。,j=4,时，,k,可能取,0,、,1,、,2,或,3,，,s0s4,，且,s0s1=s3s4,，,s0s1s2s2s3s4,，,s0s1s2s3s1s2s3s4,，所以取,k=1,，,next4=1,。其余类推。,求,s,的各字符的失败链接值算法：,引入数组,next,，元素个数为,S,的长度，依次存放,S,各字符的失败链接值。先置,next0=-1,，在已求得,next0,，,，,nextj-1,的情况下，求,nextj.,如,nextj-1=k,又有,sk=sj-1,，那末置,nextj,为,nextj-1+1;,如果,sksj-1,，令,k1=nextk,如有,sk1=sj-1,则置,nextj,为,k1+1;,如果,sk1sj-1,则按,sk1,的失败链接值再继续寻找，直至找到一个失败链接值,kn,使得,skn=sj-1,，或者,kn=-1,，这时就置,nextj=kn+1,。,【,函数,】,寻找模式各字符失败链接值的函数,void faillink(char*s,int next),int j,k;,next0=-1;,for(j=1;sj!=0;j+)k=nextj-1;,while(k!=-1&sk+1!=sj),k=nextk;,if(sj=sk+1)nextj=k+1;,else nextj=-1;,【,函数,】KMP,模式匹配函数,char*kmpMatch(char*t,char*s,int next),int k,j;,k=j=0;,while(sj!=0&tk!=0),if(sj=tk)k+;j+;,else if(j=0)k+;,else j=nextj-1+1;,if(sj=0)return t+k-j;,return NULL;,7.3 Boyer-Moore,算法,Boyer-Moore,（简称,BM,）算法同,KMP,算法类似，在匹配之前先对模式的特征进行分析，并在匹配过程中充分利用模式的特性，从而提高匹配速度。但,BM,算法有两点改进，一是对模式的分析方向是从后向前，二是进一步考虑正文中可能出现的字符。其中第二点改进有特别的好处，当正文中出现模式中没有的字符时，可以让模式大幅度向后滑过正文。,在,BM,算法中，确定正文某段字符列是否与模式匹配的字符比较顺序，从模式的最后一个字符开始逆序向前比较，考虑正文字符（在位置,i,处，字符,ti,）与模式,S=s,0,s,1,s,2,s,m-1,中某字符不匹配的多种可能情况如下：,(1),在模式中不存在正文字符,ti,，则下一步继续比较时，可将模式向后滑过正文,m,个字符。,(2),正文字符,ti,是模式的最后一个字符，且该字符在模式中只出现这一次，则下一步继续比较时，也可将模式向后滑过正文,m,个字符。,(3),正文字符,ti,是模式中间的某个字符，并且该字符在模式中只出现一次，它距离模式的末字符还有,d,个字符，则下一步继续比较时，可将模式后滑，让模式的末字符与正文的,i+d,位置字符对前。,(4),正文字符,ti,是模式中间的某个字符，并且该字符在模式中出现多次，其中在模式中的最后一次出现距离模式的末字符还有,d,个字符，则下一步继续比较时，同样可将模式后滑，让模式的末字符与正文的,i+d,位置字符对前。,BM,算法为模式定义了一个函数,d,，该函数将字符集上的字符映射到该字符在模式中出现的位置，即,1,至,m,上的整数。函数,d,定义如下：,(1),若,x,不在模式,S,中出现，或是模式中唯一最后出现，即,x=s,m-1,，但,xsj(0s,j,m-1),，定义,d(x)=m,；,(2),其余情况，这里,j=maxj,，,s,j,=x,，,xs,j,(0sjm-1),，定义,d(x)=m-1-j,。,从上述定义可知，除了模式中的最末唯一出现字符及不在模式中出现的字符,d,等于,m,外，模式中的其它字符,d,给出了该字符到模式末端的距离。如设,S=“shanghai”,，则有,d(s)=7,，,d(h)=2,，,d(a)=1,，,d(n)=4,，,d(g)=3,，,d(i)=8,，而其它字符的,d,值也都为