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

字符串(String)字符串是n(0)个字符的有限序列，记作S:“c0c1c2…cn-1”其中，S是串名字“c0c1c2…cn-1”是串值ci是串中字符n是串的长度。如：“WelcometoShanghai!!!”在计算机非数值计算应用中，经常遇到字符序列的处理。如，文字编辑、情报检索、自然语言翻译、事务处理、图象处理等应用中经常遇到的那样。在计算机中，一个字符集上的每个字符用定长的代码表示，所有可能的各种字符都可以对应一个确定的代码。一个特定的字符序列称为字符串，简称为串。有两种方法能比较方便地表示一个字符串。一是人为地约定一个特殊的代码为字符序列的结束符，每个字符串最后都有这个结束符。二是，为每个字符序列另引入一个整数，让该整数指出该字符串的字符个数。本书采用第一种表示字符串的方法模式匹配是串的基本运算之一。有两个字符串T和Ｓ，字符串T称为正文，字符串S称为模式，要求找出模式S在正文T中的首次出现的位置。一旦模式S在正文T中找到，就说发生一次匹配。有些应用可能会要求找出所有的匹配位置。串的模式匹配定义在串中寻找子串（第一个字符）在串中的位置词汇在模式匹配中，子串称为模式，串称为目标。示例目标T:“Beijing”模式P:“jin”匹配结果=3记正文T的字符个数为n，令T=t0t1t2…tn-1，记模式S的字符个数为m，令S=s0s1s2…sm-1。若正文中自位置k开始有一次匹配，则有sj=tk+j，0=jm。并且对所有pk，没有对所有的0=jm，m个等式sj=tp+j全都成立。7.1简单匹配第1趟Tabbaba穷举的模式Paba匹配过程第2趟TabbabaPaba第3趟TabbabaPaba第4趟TabbabaPabachar*stringSearch(char*t,char*p){intn=strlen(t),m=strlen(p),i,j;for(j=0;j=n-m;j++){/*从t[j]开始的子串与字符串p比较*/for(i=0;im&&t[j+i]==p[i];i++);if(i==m)returnt+j;}returnNULL;}若不考虑正文至少有模式长的字串个数，且用字符指针编写，可简写成以下形式。char*stringSearch(char*t,char*s){char*q,*p;for(;*t!=‘\0’;t++)for(q=t,p=s;*p!=‘\0’&&*q==*p;q++,p++){}return*p==‘\0’?t:NULL;}目标TSTUDENSTUDENT……‖‖‖‖‖‖模式patSTUDENT目标TSTUDENSTUDENT……模式patSTUDENT……目标TSTUDENSTUDENT……‖‖‖‖‖‖‖模式patSTUDENT简单模式匹配的缺点:无谓比较目标TFIFIFIYUDENT……‖‖‖‖模式patFIFIY目标TFIFIFIYUDENT……‖‖模式patFIFIY直接跳过错过成功比较目标TFIFIFIYUDENT……‖‖‖‖‖模式patFIFIY直接跳过子串可能错过成功比较穷举的模式匹配算法时间代价：最坏情况比较n-m+1趟，每趟比较m次，总比较次数达(n-m+1)*m原因在于每趟重新比较时，目标串的检测指针要回退。改进的模式匹配算法可使目标串的检测指针每趟不回退。改进的模式匹配(KMP)算法的时间代价：若每趟第一个不匹配，比较n-m+1趟，总比较次数最坏达(n-m)+m=n若每趟第m个不匹配，总比较次数最坏亦达到n7.2KMP算法目标Tt0t1t2……tj-1tj……tn-1‖‖‖‖X模式patp0p1p2……pj-1pj……pm-1目标Tt0t1…tk……tn-1模式patp0p1……pm-2pm-1改进的模式匹配：寻找最大“跳跃”Tt0…ts-1tsts+1ts+2…ts+j-1ts+jts+j+1…tn-1‖‖‖‖‖Pp0p1p2…pj-1pjpj+1则有tsts+1ts+2…ts+j=p0p1p2…pj(1)为使模式P与目标T匹配，必须满足p0p1p2…pj-1…pm-1=ts+1ts+2ts+3…ts+j…ts+m如果p0p1…pj-1p1p2…pj(2)则立刻可以断定p0p1…pj-1ts+1ts+2…ts+j下一趟必不匹配同样，若p0p1…pj-2p2p3…pj则再下一趟也不匹配，因为有p0p1…pj-2ts+2ts+3…ts+j直到对于某一个“k”值，使得p0p1…pk+1pj-k-1pj-k…pj且p0p1…pk=pj-kpj-k+1…pj则p0p1…pk=ts+j-kts+j-k+1…ts+j‖‖‖pj-kpj-k+1…pj因此，当正文T在t[j+i]比较失败时，正文t的扫视指针j不回溯，仍指向上一趟匹配失败的字符，即从此处开始继续比较，而模式s扫视指针i回退到k，即模式从s[k]开始，这就省去了前面的k次比较。如果对应s[i]的k有多个，应取最大的k。这样，在匹配比较过程中，一旦出现s[i]≠t[j+i]时，就要找出s[i]对应的k，称k为s[i]的失败链接值。寻找s的各字符的失败链接值，只与模式S本身有关，与正文T无关。设模式S=s0s1…sm-1，则它各字符的失败链接值next[j]的定义如下：k，当0skj，且使得s0s1…sk=sj-ksj-k+1…sj的最大整数next[j]=-1，其它情况称s0s1…sk为s0s1…sj-1sj的前缀子串，sj-ksj-k+1…sj为s0s1…sj-1sj的后缀子串。设模式S=“xyxxyzxz”，按上述公式求得各字符的失败链接值如表7.1所示。表7.1字符失败链接值J01234567SxyxxyZxznext[j]-1-1001-10-1j=0时，没有满足0skj的k存在，next[0]=-1。j=1时，可取k=0，但s0≠s1，k不符合要求，next[1]=-1。j=2时，k可能取0或1，s0=s2，且s0s1≠s1s2，所以，k=0，next[2]=0。j=3时，k可能取0、1或2，s0=s3，且s0s1≠s2s3，s0s1s2≠s1s2s3，所以取k=0，next[3]=0。j=4时，k可能取0、1、2或3，s0≠s4，且s0s1=s3s4，s0s1s2≠s2s3s4，s0s1s2s3≠s1s2s3s4，所以取k=1，next[4]=1。其余类推。求s的各字符的失败链接值算法：引入数组next[]，元素个数为S的长度，依次存放S各字符的失败链接值。先置next[0]=-1，在已求得next[0]，…，next[j-1]的情况下，求next[j].如next[j-1]=k,又有s[k]=s[j-1]，那末置next[j]为next[j-1]+1;如果s[k]≠s[j-1]，令k1=next[k],如有s[k1]=s[j-1],则置next[j]为k1+1;如果s[k1]≠s[j-1],则按s[k1]的失败链接值再继续寻找，直至找到一个失败链接值kn,使得s[kn]=s[j-1]，或者kn=-1，这时就置next[j]=kn+1。【函数】寻找模式各字符失败链接值的函数voidfaillink(char*s,intnext[]){intj,k;next[0]=-1;for(j=1;s[j]!='\0';j++){k=next[j-1];while(k!=-1&&s[k+1]!=s[j])k=next[k];if(s[j]==s[k+1])next[j]=k+1;elsenext[j]=-1;}}【函数】KMP模式匹配函数char*kmpMatch(char*t,char*s,intnext[]){intk,j;k=j=0;while(s[j]!='\0'&&t[k]!='\0')if(s[j]==t[k]){k++;j++;}elseif(j==0)k++;elsej=next[j-1]+1;if(s[j]=='\0')returnt+k-j;returnNULL;}7.3Boyer-Moore算法Boyer-Moore（简称BM）算法同KMP算法类似，在匹配之前先对模式的特征进行分析，并在匹配过程中充分利用模式的特性，从而提高匹配速度。但BM算法有两点改进，一是对模式的分析方向是从后向前，二是进一步考虑正文中可能出现的字符。其中第二点改进有特别的好处，当正文中出现模式中没有的字符时，可以让模式大幅度向后滑过正文。在BM算法中，确定正文某段字符列是否与模式匹配的字符比较顺序，从模式的最后一个字符开始逆序向前比较，考虑正文字符（在位置i处，字符ti）与模式S=s0s1s2…sm-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=sm-1，但x≠sj(0sjm-1)，定义d(x)=m；(2)其余情况，这里j=max{j，sj=x，x≠sj(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值也都为8。BM算法的基本要点是：(1)对正文中可能出现的每个字符根据该字符在模式中的出现位置，定义函数d，并用数组d[]存储对应字符的函数值。确定正文某段字符列是否能与模式匹配的字符比较顺序是，从模式的最后一个字符开始逆序向前比较。一旦发现正文字符ti与当时模式中的对应字符不匹配时，则模式在正文上后滑，下一步继续比较从sm-1与正文i+d(ti)位置字符起始，自后逆序向前匹配检查。计算d的算法如下：voidcalculateD(intd[],char*s,intm){intk;for(k=0;k256;k++)d[k]=m;for(k=m-2;k=0;k--)if(d[s[k]]==m)d[s[k]]=m-k+1;}BM算法如下：char*bmMatch(char*t,char*s){intk,j,i,m=strlen(s),n=strlen(t);intd[256];calculateD(d,s);i=m-1;do{j=m-1;k=i;while(j=0&&s[j]==t[k]){j--;k--;}i+=d[t[i]];}while(j=0&&i=n);if(j0)returnt+k+1;returnNULL;}算法分析上述计算d的算法的运行时间为Θ(m)，BM算法的最坏情况在每轮匹配比较了m个字符后才失败的情况下发生，运行时间为Θ(mn)。第七章结束