4 串

1Chapter4串YuxiangzhangComputerScienceDepartment,CAUC,[e-mail]2Contents1字符串与线性表2字符串的五个基本操作3串的模式匹配算法31.字符串与线性表串(String)是零个或多个字符组成的有限序列线性表的基本操作大多以“单个元素”为操作对象，而串的基本操作通常以“串的整体”作为操作对象。思维Good!42.字符串的五个基本操作思维Good!(1)求串长(length)intstrlen(char*s);(2)串复制(copy)char*strcpy(char*to,char*from);(3)联接(concatenation)char*strcat(char*to,char*from)5(4)串比较(compare)intstrcmp(char*s1,*chars2);(5)字符定位(index)char*strchr(char*s,charc);上述串的操作是最基本的，其中后四个还有变种形式：strncpy，strncat，strncmp，strnchr。串的其余操作可由这些基本操作组合而成。63.串的模式匹配算法模式匹配在“目标串T”中查找与“模式串P”相同“子串”的过程。如果在T中找到等于P的子串，则称匹配成功，函数返回P在T中的首次出现的存储位置(或序号)，否则匹配失败，返回-1。例如：目标串T：“Beijing”；模式串P：“jin”。匹配结果=31．简单的模式匹配（BF）算法7设主串T=“ababcabcacbab”，模式P=“abcac”。89//BF算法实现，s目标串，t模式串intBF(strtypes,strtypet){inti,j,k;for(i=0;s.str[i];i++)for(j=i,k=0;s.str[j]==t.str[k];j++,k++)if(!t.str[k+1])//保证串t被扫描完return(i);return(-1);}保证每个字符相同strtypes,t;Assign(&s,aababababad);Assign(&t,bab);cout(Index(s,t));//2102．BF算法能否改进？分析BF算法的特点：在某趟的匹配过程失败后，对于目标串T要回到本趟开始字符的下一个字符，模式串P要回到第一个字符。Newidea：下一个字符下几个字符113．进一步分析BF算法设主串T=“ababcabcacbab”，模式P=“abcac”。当b!=c时，但它们前面的5个字符是相等的，所以向后跳多远，只要分析红线中间部分字符串就可以，也就是只要分析模式串出现不匹配字符的前面字符串就可以。转移关注对象12当b!=c时，只分析模式串(由上面分析得)，最差情况下后移一位(绿线)，最好情况下后移多位，将第一个元素移过来比较(蓝线)，设主串T=“ababcabcacbab”，模式P=“abcac”。13当b!=c时，只分析模式串(由上面分析得)，From(绿线)To(红线)，设主串T=“ababcabcacbab”，模式P=“abcac”。1234j=5,移第4个元素和b进行比较，记为Next[j]=4，若可以这样移动要满足What特征？14j=5,移第3个元素和b进行比较，记为Next[j]=3，若可以这样移动要满足What特征？当b!=c时，只分析模式串(由上面分析得)，From(绿线)To(红线)，设主串T=“ababcabcacbab”，模式P=“abcac”。1234151234012j=5，Next[j]=4绿线，最差情况j=5，Next[j]=3161234034j=5，Next[j]=2j=5，Next[j]=1蓝线，最好情况17KMP算法1977年Knuth、Morris和Pratt提出了著名的KMP算法【D.E.Knuth,J.H.Morris,andV.R.Pratt,“Fastpatternmatchinginstrings,”SIAMJournalonComputing,vol.6,pp.323~350】KMP算法的思想：每当一趟匹配过程中出现字符比较不等时，不需指针回溯，而是利用得到的部分匹配的结果，将模式向右滑动尽可能远的一段距离后，继续进行比较。18最差最远最差最远19(1)求模式串中字符j的next值：Next[j]意义：当匹配过程中产生失配(tipj)时，将模式串“向右移动”至模式中的第“k”个字符和主串中的第i个字符对齐，如何确定“k”？模式串移动见下图：Tt1t2…ti-k+1ti-k+2………ti-1ti‖Pp1…pj-k+1pj-k+2……pj-1pjPp1p2………pk-1pk…pj-1pj–模式串中前“k-1”个字符满足下式，且不存在k’k：‘p1p2…pk-1’=‘ti-k+1ti-k+2………ti-1’(1)–已经得到的“部分匹配”的结果是：‘pj-k+1pj-k+2…pj-1’=‘ti-k+1ti-k+2………ti-1’(2)20由(1)和(2)推得：‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’令：k=next[j]，则next的函数定义如下：j2andp1pj-1j=2or21j123456模式串abaabcnext[j]K值应从大到小计算j1234567模式串ababcacnext[j]011223011231222由定义知：next[1]=0；假设：next[j]=k，即有：“p1…pk-1”=“pj-k+1…pj-1”，(1kj)，且不存在k’k使上式成立。求next[j+1]=？分两种情况：(1)若pk=pj，则next[j+1]=next[j]+1表明：“p1…pk-1pk”=“pj-k+1…pj-1pj”(2)求next[j]的递推算法j12j=3456模式串abaabck=next[j]011?k==023(2)若pkpj，表明在模式串中“p1…pk-1pk”“pj-k+1…pj-1pj”即p1…pj-k+1…pj-1pj”(比对)‖‖p1…pk-1pk(k=next[j])(比对)‖p1…pk(k=next[k])Continue…(k=next[k])直到某一k，使pj=pk或k=0为止。j123456模式串abaabcnext[j]0112?实质上：也是模式匹配24已知：next[1]=0；假设：next[j]=k；(1)若：k==0或P[j]==P[k]，则：next[j+1]=k+1；(2)若：P[j]!=P[k]，则需往前回朔：k=next[k]，执行(1)。求next[j]的递推算法总结如下：实质上：也是一个匹配的过程；不同在于：主串和模式串是同一个串。25/*求模式串的next值并存入next数组中*/voidGetNext(char*p,intnext[]){inti=1,k=0;next[1]=0;while(j=p[0]){if(k==0||p[j]==p[k]){++j;++k;next[j]=k;}//p[j]与p[next[k]]比对，向前递推elsek=next[k];}}存储字符个数26(3)next[j]是否完美无缺？例如：T=‘aaabaaaab’S=‘aaaab’next[j]=01234KMP算法：Taaabaaaab(i=4)Saaaa(p[4]失配，k应取3，进行比对)aaaa(其实不必比对k=3,2,1，因p[4]=p[3]，p[4]失配，则p[3]失配必失配。)启示：当k=next[j]时，有必要比对p[j]与p[k]，因若p[j]==p[k]，p[j]失配，则p[k]必失配，不必比对p[k]。故当p[j]==p[k]时，next[j]=next[k]。nextval[j]=0000427/*求模式串的nextval值并存入该数组中*/voidGetNext(char*p,intnextval[]){inti=1,k=0;nextval[1]=0;while(j=p[0]){if(k==0||p[j]==p[k]){++j;++k;if(p[j]!=p[k])nextval[j]=k;elsenextval[j]=nextval[k];}elsek=nextval[k];}}28(1)KMP算法基本思想：当T[i]和p[j]失配时，在1至j-1中确定p[k]与T[i]比对。(2)KMP算法中next[j]计算公式：(3)KMP算法中next[j]算法实现：向前模式匹配法。(4)KMP算法中nextval[j]算法实现：当p[j]==p[k=next[j]]时，p[j]失配，则p[k]必失配，故应向前寻找和p[next[k]]比对，于是nextval[j]=nextval[k]。总结：29#includeiostream.h#includestring.htypedefstruct{char*s;//目标char*t;//模式int*next;//存储next值}kmpstring;voidinit(kmpstring&ks,char*ss,char*tt){intn=strlen(ss);intm=strlen(tt);ks.s=newchar[n+1];ks.s[0]=n;for(inti=1;i=n;i++)ks.s[i]=ss[i-1];ks.t=newchar[m+1];ks.t[0]=m;for(intj=1;j=m;j++)ks.t[j]=tt[j-1];}//初始化目标和模式30//获得模式串的next值voidget_next(kmpstring&ks,charp[]){inti(1),j(0);intn=strlen(p);ks.next=newint[n+1];ks.next[0]=9999;ks.next[1]=0;while(i=(int)(ks.t[0])){if(j==0||ks.t[i]==ks.t[j]){++i;++j;ks.next[i]=j;}elsej=ks.next[j];}}//初始化next数组31假设以指针i和j分别指示主串和模式中的比较字符，令i的初值为pos，j的初值为1。若在匹配过程中ti=pj，则i和j分别增１，否则(tipj)，则i不变，j退到next[j]位置再比较，若相等，则指针各自增１，否则j再退到下一个next值的位置，依此类推。(作循环)在j值回退中，当j退到值为零（即模式的第一个字符失配），则此时i和j也要分别增１，表明从主串的下一个字符ti+1起和模式重新开始匹配。(添加循环条件)KMP算法的时间复杂度可达到O(m+n)(3)求得模式的next函数之后，匹配如下：32↓i=2第一趟匹配：主串acabaabaabcacaabc模式串ab↑j=2next[2]=1↓i=2第二趟匹配：主串acabaabaabcacaabc模式串a↑j=1next[1]=0↓i=3→↓i=8第三趟匹配：主串acabaabaabcacaabc模式串abaabc↑j=1→↑j=6next[6]=3↓i=8→↓i=12第四趟匹配：主串acabaabaabcacaabc模式串(ab)aabc↑j=3→↑j=733//利用模式串P的next函数，求P在主串T中的位置(P非空)intkmp(kmpstringks,intpos)//从pos位置开始{inti=pos,j=1;while(i=((int)(ks.s[0]))&&(j=((int)(ks.t[0])))){if((j==0)||(ks.s[i]==ks.t[j])){++i;++j;}elsej=ks.next[j];//模式串向右移动}if(j(int)(ks.t[0]))returni-((int)(ks.t[0]));elsereturn0;}34