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

4 串4.1 串的匹配子串的定位操作称为串的模式匹配，是各种串处理中最重要的操作。在主字符串s中查找模式字符串p，若在主串中找到等于模式串的子串，称为匹配成功，返回与模式串第一个相等的字符在主串中的序号；若匹配不成功，则返回0。4.1.1 串的简单匹配串的简单匹配，基本思想是：从主串的第一个字符起和模式串的第一个字符比较，若相等，则继续逐个比较后续的字符，否则从主串的第二个字符起再重新和模式串的字符比较。依此类推，直至模式串的每个字符依次和主串中的一个连续的字符序列相等，则为匹配成功【例4-1-1】： 主串：a b a b c a b c a c b a b匹配串：a b c a c i =3第一趟匹配： a b a b c a b c a c b a b a b c j =3 i=2第二趟匹配： a b a b c a b c a c b a b a j=1 i=7第三趟匹配： a b a b c a b c a c b a b a b c a c j=5 i=4第四趟匹配： a b a b c a b c a c b a b a j=1 i=5第五趟匹配： a b a b c a b c a c b a b a j=1 i=11第六趟匹配： a b a b c a b c a c b a b a b c a c 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第一趟匹配：a b a b c a b c a c b a ba b cj=3i=7第二趟匹配：a b a b c a b c a c b a ba b c a cj=5i=11第三趟匹配：a b a b c a b c a c b a ba b c a cj=6kmp算法的基本思想是:在匹配过程中，当 sipj 时，应在模式串p的开头和主串s紧靠i之前找到相等的最大子串，子串长度为k 1，如图所示：jpkk-1is然后将模式串向右滑动，比较si和pk是否相等。对于kmp算法，需要解决的问题首先是：当匹配过程产生“失配”，模式串“向右滑动”可行多远？换句话说，当主串中第i个字符与模式串中第j个字符“失配”（即不相等）时，主串中第i个字符应与模式串中哪个字符再比较？（二）求证k仅与模式串相关设主串为s，模式串为p。假设当主串中第i个字符与模式串中第j个字符“失配”时，主串的第i个字符应与模式串的第k个字符继续比较，则模式串中前j个字符必须满足下列关系：p1p2pk-1si - k+1si - k+2si-1 （1） 匹配串p的前k-1个字符与主串中第i个字符前的k-1个字符相等而已经得到“部分匹配”的结果是：pj-k+1pj-k+2pj-1si-k+1si-k+2si-1 （2）匹配串p第j个字符前的k-1个字符与主串中第i个字符前的k-1个字符相等由（1）和（2），可以推出下式：p1p2pk-1pj-k+1pj-k+2pj-1即模式串中前k-1个字符与第j-k+1到j-1个字符相等，即k仅与模式串有关，与主串无关。（三）next数组因此，我们可以设next数组，令nextj=k，则nextj表明当模式中第j个字符与主串相应字符“失配”时，主串中该字符重新与模式串中进行比较的字符的位置。next数组的定义： 0 当 j=1时 nextj= max k | 1kj 且 p1pk-1=pj-k+1pj-1 当此集合不空时1 其它情况 【例4.1.2_1】 j1 2 3 4 5 6 7 8模式串next j a b a a b c a c0 1 1 2 2 3 1 2next数组怎样具体求得，我们这里先放一下，先看看在设了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起和模式串重新开始匹配。算法如下：function kmp:integer； 假设已求出next数组begin i:=1； j:=1； 指针初始化 while (i=s.length) and (jp.length then kmp:=i-p.length 匹配成功 else kmp:=0；end；（五）求next数组的算法从上述讨论已知，next数组的值仅与模式串本身有关，而与相匹配的主 串无关，我们可以根据模式串，从分析其定义出发，用递推的方法求得next数组的值。由定义知： next 1 = 0设已求得 next j = k ，求next j+1 = ? 有两种情况：1若pk = pj ，则表明在模式串中：p1pkpj - k+1pj就是说 next j+1 = k+1 ，即：next j+1 = next j +12若pkpj，则表明在模式串中：p1pkpj k+1pj此时如何处理？procedure next; var i , j , k ：integer; begin next 1 := 0；k := 0；for j := 1 to p_length -1 do p_length为模式串p的长度 begin if （k = 0） or （pj = pk） then begin endelse begin end； end； end； 参考答案： k := k+1；next j+1 := k； repeat k := next k； until（k=0）or（pj=pk）； k := k+1； next j+1 := k； 求next数组程序2：procedure next； var j , k ：integer； begin j := 1； k := 0； next1 := 0； while j p_length do if（k=0）or（pj=pk） then begin j := j+1； k := k+1； nextj := k； end else k := nextk； end； 另一种求next数组的算法： procedure next； readln (p)； next1:= 0； for j:=2 to p_length do begin k := j-1； repeat k:=k-1； until copy(p,1,k) = copy(p,j-k,k)； nextj := k+1； end； end； （六）进一步优化：前面定义的next函数在某些情况下尚有缺陷，例如：模式串p=aaaab和主串s=aaabaaaab匹配当i=4，j=4，s4p4时，由nextj的指示，模式串向右移，s4还要与p3、p2、p1继续比较。实际上，因为模式串中第1、2、3个字符和第4个字符都相等，没必要再和s4相比较，可将模式串直接向右滑动4个字符，进行i=5、j=1时的比较。为了克服这种不必要的重复比较，对求next的算法进行改进，其基本思想是：在求得j点的k值后，在判断pk和pj是否相等，若相等则把nextvalk值送nextvalj中，否则把原来的k值存入nextvalj中。表中的nextvalj就是改进后的值。j 1 2 3 4 5 6 7 8 9 10 11模式串p a b c a b c a b b a cnextj 0 1 1 1 2 3 4 5 6 1 2nextvalj 0 1 1 0 1 1 0 1 6 0 2算法为： procedure next2； var j,k ：integer； begin j:= 1； k := 0； nextval1 := 0； while j0）and（sk = pj）do begin j := j 1； k := k 1； end； if j0 then i := i + nextb si ； until （j = 0）or（j n）； if j = 0 then bm_match := i m + 1 else bm_match := 0； end；4.1.3 串的广义匹配设主串s和模式串p，按模式串中字符顺序在主串中顺序找到但不一定连续与模式串相同的字符序列，称之为广义匹配。广义匹配具有许多的用途，如数据库的模糊查询等。 例如： 主串s= a c d a c b e m 模式串p=d c b s: a c d a c b e m p: d c b 显然有 s3s5s6p1p2p3参考算法如下，它主要适用于ascii码字符和汉字字符。 program gypp； var p , s : string； i , j , k : integer； d : array 1 . . 260 of integer；begin write ( p: )； readln (p)； write ( s: )； readln (s)； i := 1； j := 0； while i=length(s) do begin if pj+1=si then begin j := j+1； dj := i； i := i+1； end else i := i+1； end； if j=0 then writeln (no find) else for k:=1 to j do write (dk:3)；end.【综合练习】1、 求回文数若一个数（首位不为零）从左向右读与从右向左读都是一样，则称为回文数。有一种求回文数的方法：例如，给定一个十进制整数56，将56加65（即把56从右向左读），得到的121是一个回文数；又如，对于十进制数87，按以上方法用4步可以得到回文数4884。step1: 87+78=165 step2:=165+561=726step3: 726+627=135