广东省汕头市金山中学高中信息技术竞赛班数据结构专项培训教程04串教案

§4串§4.1串的匹配子串的定位操作称为串的模式匹配，是各种串处理中最重要的操作。在主字符串S中查找模式字符串P，若在主串中找到等于模式串的子串，称为匹配成功，返回与模式串第一个相等的字符在主串中的序号；若匹配不成功，则返回0。§4.1.1串的简单匹配串的简单匹配，基本思想是：从主串的第一个字符起和模式串的第一个字符比较，若相等，则继续逐个比较后续的字符，否则从主串的第二个字符起再重新和模式串的字符比较。依此类推，直至模式串的每个字符依次和主串中的一个连续的字符序列相等，则为匹配成功……【例4-1-1】：主串：ababcabcacbab匹配串：abcac↓i=3第一趟匹配：ababcabcacbababc↑j=3↓i=2第二趟匹配：ababcabcacbaba↑j=1↓i=7第三趟匹配：ababcabcacbababcac↑j=5↓i=4第四趟匹配：ababcabcacbaba↑j=1↓i=5第五趟匹配：ababcabcacbaba↑j=1↓i=11第六趟匹配：ababcabcacbababcac↑j=6这种算法易于理解，在某些场合效率也较高。但当主串为‘000000000000000000000000000000000000000000000000001’，模式串为‘00000001’时，由于模式串中前7各字符均为‘0’，主串中前50各字符均为‘0’，每趟比较都在模式串的最后一个字符出现不等，此时需将指针i回溯到i-6的位置上，并从模式的第一个字符开始重新比较。直到匹配成功，指针i需回溯43次。这经常出现在主串中存在多个子串和模式串“部分匹配”的情况下，例如01串（字符串由0、1组成）。§4.1.2串的KMP匹配算法这种改进的算法是由D.E.Knuth、V.R.Pratt和J.H.Morris三人同时发现的，所以称为KMP算法。（一）KMP算法的基本思路KMP算法每当一趟匹配过程中发现字符不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。先回顾简单匹配的算法，从例4-1-1可以看出，在第三趟匹配中，当i=7、j=5字符比较不等时，又从i=4、j=1重新比较。而在i=4和j=1，i=5和j=1，以及i=6和j=1这三次比较都是不必要的。因为从第三趟部分匹配的结果可以看出，主串中第4、5、6个字符必然是’b’、’c’、’a’（即模式串中第2、3、4个字符）。因为模式串中第一个字符是a，因为它无需和这三个字符进行比较，所以仅需将模式串向右滑动三个字符的位置进行比较。同理，在第一趟匹配中出现字符不等时，仅需将模式串向右移动2个字符的位置继续进行i=3、j=1时的字符比较。由此，整个过程指针i没有回溯，如下所示。↓i=3第一趟匹配：ababcabcacbababc↑j=3↓i=7第二趟匹配：ababcabcacbababcac↑j=5↓i=11第三趟匹配：ababcabcacbababcac↑j=6KMP算法的基本思想是:在匹配过程中，当Si≠Pj时，应在模式串P的开头和主串S紧靠i之前找到相等的最大子串，子串长度为k–1，如图所示：然后将模式串向右滑动，比较Si和Pk是否相等。对于KMP算法，需要解决的问题首先是：当匹配过程产生“失配”，模式串“向右滑动”可行多远？换句话说，当主串中第i个字符与模式串中第j个字符“失配”（即不相等）时，主串中第i个字符应与模式串中哪个字符再比较？jPkk-1iS（二）求证k仅与模式串相关设主串为S，模式串为P。假设当主串中第i个字符与模式串中第j个字符“失配”时，主串的第i个字符应与模式串的第k个字符继续比较，则模式串中前j个字符必须满足下列关系：‘P1P2……Pk-1’＝‘Si-k+1Si-k+2……Si-1’（1）{匹配串P的前k-1个字符与主串中第i个字符前的k-1个字符相等}而已经得到“部分匹配”的结果是：‘Pj-k+1Pj-k+2……Pj-1’＝‘Si-k+1Si-k+2……Si-1’（2）{匹配串P第j个字符前的k-1个字符与主串中第i个字符前的k-1个字符相等}由（1）和（2），可以推出下式：‘P1P2……Pk-1’＝‘Pj-k+1Pj-k+2……Pj-1’即模式串中前k-1个字符与第j-k+1到j-1个字符相等，即k仅与模式串有关，与主．串无关．．．。（三）next数组因此，我们可以设next数组，令next[j]=k，则next[j]表明当模式中第j个字符与主串相应字符“失配”时，主串中该字符重新与模式串中进行比较的字符的位置。Next数组的定义：0当j=1时next[j]=Max{k|1kj且‘p1……pk-1’=‘pj-k+1……pj-1’}当此集合不空时1其它情况【例4.1.2_1】j12345678模式串next[j]abaabcac01122312Next数组怎样具体求得，我们这里先放一下，先看看在设了next数组后KMP匹配的算法，这可能将更有利于理解。（四）KMP算法匹配可如下进行：①指针i和j分别指示主串和模式串中正待比较的字符，令i和j的初值皆为1。②若在匹配过程中si=pi，则i和j分别增1，否则j再退到下一个next值的位置，依此类推，直至下列可能：一种是j退到某个next（next[next[…next[j]]]）值时字符比较相等，则指针各自增1继续进行匹配（模式串滑动）；另一种是j退到next值为0（即模式的第一个字符“失配”），则此时需将模式串继续向右滑动一个位置，从主串的下一个字符si+1起和模式串重新开始匹配。算法如下：functionKMP:integer；……{假设已求出next数组}begini:=1；j:=1；{指针初始化}while(i=s.length)and(j=p.length)do{s.length、p.length分别为主串和模式串的长度}if（j=0）or（s[i]=p[i]）thenbegini:=i+1；j:=j+1；{继续下一对字符的比较}endelsej:=next[j]；{模式串向右滑动}ifjp.lengththenKMP:=i-p.length{匹配成功}elseKMP:=0；end；（五）求next数组的算法从上述讨论已知，next数组的值仅与模式串本身有关，而与相匹配的主串无关，我们可以根据模式串，从分析其定义出发，用递推的方法求得next数组的值。由定义知：next[1]=0设已求得next[j]=k，求next[j+1]=?有两种情况：1．若Pk=Pj，则表明在模式串中：‘P1……Pk’＝‘Pj-k+1……Pj’就是说next[j+1]=k+1，即：next[j+1]=next[j]+12．若Pk≠Pj，则表明在模式串中：‘P1……Pk’≠‘Pj–k+1……Pj’此时如何处理？procedurenext;vari,j,k：integer;beginnext[1]:=0；k:=0；forj:=1top_length-1do{p_length为模式串P的长度}beginif（k=0）or（P[j]=P[k]）thenbeginendelsebeginend；end；end；参考答案：①k:=k+1；next[j+1]:=k；②repeatk:=next[k]；until（k=0）or（P[j]=P[k]）；k:=k+1；next[j+1]:=k；求next数组程序2：procedurenext；varj,k：integer；beginj:=1；k:=0；next[1]:=0；whilejp_lengthdoif（k=0）or（P[j]=P[k]）thenbeginj:=j+1；k:=k+1；next[j]:=k；endelsek:=next[k]；end；另一种求next数组的算法：procedurenext；readln(p)；next[1]:=0；forj:=2top_lengthdobegink:=j-1；repeatk:=k-1；untilcopy(p,1,k)=copy(p,j-k,k)；next[j]:=k+1；end；end；（六）进一步优化：前面定义的next函数在某些情况下尚有缺陷，例如：模式串P=‘aaaab’和主串S=‘aaabaaaab’匹配当i=4，j=4，S[4]≠P[4]时，由next[j]的指示，模式串向右移，S[4]还要与P[3]、P[2]、P[1]继续比较。实际上，因为模式串中第1、2、3个字符和第4个字符都相等，没必要再和S[4]相比较，可将模式串直接向右滑动4个字符，进行i=5、j=1时的比较。为了克服这种不必要的重复比较，对求next的算法进行改进，其基本思想是：在求得j点的k值后，在判断P[k]和P[j]是否相等，若相等则把nextval[k]值送nextval[j]中，否则把原来的k值存入nextval[j]中。表中的nextval[j]就是改进后的值。算法为：procedurenext2；varj,k：integer；beginj:=1；k:=0；nextval[1]:=0；whilejp_lengthdoif（k=0）or（P[j]=P[k]）thenbeginj:=j+1；k:=k+1；ifP[j]=P[k]thennextval[j]:=nextval[k]elsenextval[j]:=k；j1234567891011模式串Pabcabcabbacnext[j]01112345612nextval[j]01101101602endelsek:=nextval[k]；end；§4.1.3串的BM匹配算法在实际的模式匹配中，往往失配的机会反而比匹配的机会要多，针对这种情况，BM（Boyer-Moore）采取从模式串末端往前匹配的算法，简称BM算法。实现这个算法首先是求出模式串的nextb数组值，然后进行模式匹配。（1）求nextb数组值基本思想：把模式串中每个字符（称ch）至模式串最末尾字符的距离（若模式串中有相同的字符，只记下离尾端最近的那个字符的距离）分别存放到每个字符所对应的nextb[ch]中，不在模式串中出现的字符，其nextb[ch]值为模式串长m。nextb[ch]m或nextb[ord(ch)]m-max{j|1≤j≤m-1且pj=ch}为讨论的简单起见，设串都是小写字母，例如有模式串P＝‘abcdcfd’，长度m＝7，其nextb数组中值如表所示。其中nextb[‘g’]至nextb[‘z’]的值均为7。chabcdefgh……znextb[ch]65237177……7算法：typecar=array[‘a’..‘z’]ofinteger；……procedurenextb（p:string；varnextb:car）；vari:char；j,m:integer；beginm:=p_length；fori:=‘a’to‘z’donextb[i]:=m；forj:=1tom-1donextb[p[j]]:=m-j；end；（2）BM匹配算法基本思想：从模式串P尾端字符和主串S相对应位字符开始比较，若相等则继续往前（向左）逐个比较，否则将串P右移nextb[ch]位（此处ch是模式串P尾端字符相对应主串S中的相应字符），然后从P的尾端字符和S中相对应的字符重新开始比较，若相等则继续往前比，依此类推，直至最后匹配成功或失败为止。【例】714↓↓S：aytuklmabopwacneabcdcfdhs╫＝P：abcdcfd╫P右移7位后：abcdcfd╫P右移2位后：abcdcfdP右移7位后：abcdcfdhs算法如下：functionBM_match（s,p:string；nextb:car）:integer；vari,j,k,m,n:integer；beginm:=p_length；n:=s_length；i:=m；repeatj:=m；k:=i；while（j0）and（s[k]=p[j]）dobeginj:=j–1；k:=k–1；end；ifj