數(shù)據(jù)結(jié)構(gòu)與算法：線性表

字符串:模式匹配

模式匹配：在一個(gè)字符串（主串）中定位另一個(gè)串（子串，模式）基本方法：將主串S中某個(gè)位置i起始的子串和模式串T相比較。即從j=0

起比較S[i+j]

與T[j]，若相等，則在主串S

中存在以i為起始位置匹配成功的可能性，繼續(xù)往后比較(j逐步增1)，直至與T串中最后一個(gè)字符相等為止，否則改從S串的下一個(gè)字符起重新開始進(jìn)行下一輪的“匹配”，即將串T向后滑動(dòng)一位，即

i

增1，而

j

退回至0，重新開始新一輪的匹配。當(dāng)這樣一個(gè)失配發(fā)生時(shí)，T下標(biāo)必須回溯到開始，S下標(biāo)回溯的長(zhǎng)度與T相同，然后S下標(biāo)增1,然后再次比較。例如：在串S=”abcabcabdabba”中查找T=”abcabd”:先是比較S[0]和T[0]是否相等，然后比較S[1]和T[1]是否相等…我們發(fā)現(xiàn)一直比較到S[5]和T[5]才不等。這次立刻發(fā)生了失配，T下標(biāo)又回溯到開始，S下標(biāo)增1,然后再次比較。失配匹配intIndex_BF(charS[],charT[],intpos){inti=pos,j=0;while(S[i+j]!='\0'&&T[j]!='\0')if(S[i+j]==T[j])j++;//繼續(xù)比較后一字符

else{i++;j=0;//重新開始新的一輪匹配

}if(T[j]=='\0')returni;//匹配成功返回下標(biāo)

elsereturn-1;//串S中(第pos個(gè)字符起)不存在和串T相同的子串}//Index_BF問(wèn)題：若串S中從第pos(S的下標(biāo)0≤pos<StrLength(S))個(gè)字符起存在和串T相同的子串，則稱匹配成功，返回第一個(gè)這樣的子串在串S中的下標(biāo)，否則返回-1。最好情況：每一趟不成功的匹配都發(fā)生在第一對(duì)字符比較時(shí)，設(shè)匹配成功發(fā)生在Si處，則字符比較次數(shù)在前面i-1趟供比較了i-1次，第i趟匹配成功共比較m次，總共比較了i-1+m次。所有匹配成功的可能共有n-m+1種。設(shè)從Si開始T模式匹配成功的概率為Pi，在等概率情況下Pi=1/(n-m+1)

最好情況的比較次數(shù)是:1/(n-m+1)∑(i-1+m)，即O(n+m)ni=1設(shè)母串S的長(zhǎng)度為m，模式串T的長(zhǎng)度為n：則算法Index_BF的時(shí)間復(fù)雜度為：T(n)=O(m*n)最壞情況：每一趟不成功的匹配都發(fā)生在T的最后一個(gè)字符，設(shè)匹配成功發(fā)生在Si處，則字符比較次數(shù)在前面i-1趟供比較了(i-1)*m次，第i趟匹配成功共比較m次，總共比較了i*m次。共需要n-m+1趟比較。最壞情況的比較次數(shù)是:(n-m+1)*m

，其時(shí)間復(fù)雜度為O(n*m)

Cook于1970年證明的一個(gè)理論得到，任何一個(gè)可以使用被稱為下推自動(dòng)機(jī)的計(jì)算機(jī)抽象模型來(lái)解決的問(wèn)題，也可以使用一個(gè)實(shí)際的計(jì)算機(jī)（更精確的說(shuō)，使用一個(gè)隨機(jī)存取機(jī)）在與問(wèn)題規(guī)模對(duì)應(yīng)的時(shí)間內(nèi)解決。特別地，這個(gè)理論暗示存在著一個(gè)算法可以在大約m+n的時(shí)間內(nèi)解決模式匹配問(wèn)題。

D.R.Knuth和V.R.Pratt努力地重建了Cook的證明，由此創(chuàng)建了這個(gè)模式匹配算法。大概是同一時(shí)間，J.H.Morris在考慮設(shè)計(jì)一個(gè)文本編輯器的實(shí)際問(wèn)題的過(guò)程中創(chuàng)建了差不多是同樣的算法(克努特-莫里斯-普拉特,KMP算法)。并不是所有的算法都是“靈光一現(xiàn)”中被發(fā)現(xiàn)的，而理論化的計(jì)算機(jī)科學(xué)確實(shí)在一些時(shí)候會(huì)應(yīng)用到實(shí)際的應(yīng)用中。斯蒂芬·庫(kù)克（StephenA.Cook）：1961年從UniversityofMichigan獲得其學(xué)士學(xué)位，于1962年和1966年從哈佛大學(xué)分別獲得其碩士與博士學(xué)位。

1966年到1970年，Stephen在加州Berkeley分校擔(dān)任助理教授職務(wù)。1970年，Stephen加盟多倫多大學(xué)并工作直到現(xiàn)在。他是NP完全性理論的奠基人，1971年發(fā)表Cook定理奠定了NP完全理論的基礎(chǔ)而獲1982年圖靈獎(jiǎng)。Cook是對(duì)計(jì)算復(fù)雜性理論有突出貢獻(xiàn)的計(jì)算機(jī)科學(xué)家之一。

在1998年加盟蘋果電腦擔(dān)任全球業(yè)務(wù)高級(jí)副總裁之前，Cook先生曾任康柏(Compaq)企業(yè)材料副總裁,負(fù)責(zé)采購(gòu)、管理康柏的產(chǎn)品存貨。在這之前，Cook先生是IntelligentElectronics經(jīng)銷商部門的首席運(yùn)營(yíng)官。Cook先生還曾在IBM供職12年之久，他在IBM最近的職務(wù)為北美業(yè)務(wù)執(zhí)行主管，負(fù)責(zé)IBM的PersonalComputerCompany在北美和拉美的制造和分銷運(yùn)作。第一趟匹配

ababcabcacbababc第二趟匹配

ababcabcacbababcac第三趟匹配

ababcabcacbab(a)bcaci=2j=2i=6ij=0j=4i=10ij=1j=5s=“ababcabcacbab”,t=“abcac”需要解決的問(wèn)題：當(dāng)匹配過(guò)程中產(chǎn)生“失配”（si≠tj）時(shí)，模式串“向右滑動(dòng)”可行的距離多遠(yuǎn)？當(dāng)主串中第i

個(gè)字符與模式中第j

個(gè)字符“失配”時(shí)，主串中第

i

字符應(yīng)與模式中哪個(gè)字符再比較？acabaabaabcacaabcabi=1j=1next[1]=0主串模式第一趟acabaabaabcacaabcai=1j=0next[0]=-1主串模式第二趟acabaabaabcacaabcabaabci=2j=0j=5,next[5]=2i=7主串模式第三趟acabaabaabcacaabc(ab)aabcaci=7j=2j=8i=13主串模式第四趟-1，j=0Next[j]=Max{k|1<k<j}，“t0t1…tk-1”=“tj-kti-k+1…tj-1”0，其他情況t=“abaababc”t=“abaabcac”j01234567tabaababcnext[j]-10011232j01234567tabaabcacnext[j]-10011201

設(shè)：s=“s0s1s2…sn-1”,t=“t0t1t2…tm-1”，當(dāng)si≠tj時(shí)存在：“t0t1…tj-1”=“si-jsi-j+1…si-1”若模式串t中存在可互相重疊的最大真子串滿足：

“t0t1…tk-1”=“tj-kti-k+1…tj-1”（0<k<j）則下一次比較可直接從模式的第k+1個(gè)字符tk開始與目標(biāo)串的第i+1個(gè)字符si相對(duì)應(yīng)繼續(xù)進(jìn)行下一趟匹配。若模式串中不存在上述真子串,則下一次比較可直接從模式串的第1個(gè)字符t0開始與目標(biāo)串s的第i+1個(gè)字符si相對(duì)應(yīng)繼續(xù)進(jìn)行下一趟的匹配。voidget_next(constchar*T,intnext[]){//求模式串T的next函數(shù)值

intj=0,k=-1;next[0]=-1;while(T[j]!='\0'){if(k==-1||T[j]==T[k]){++j;++k;next[j]=k;}elsek=next[k];}//while}//get_nextintIndex_KMP(char*s,char*t,intnext[]){inti=0,j=0;while(s[i]!='\0'&&t[j]!='\0')if(j==0||s[i]==t[j]){i++;j++;}elsej=next[j];if(t[j]=='\0')returni-strlen(t);else return0;}另next[j]=k：表示主串si和子串tj失配時(shí)，應(yīng)該繼續(xù)將si與tk進(jìn)行比較。

如下例所示：當(dāng)?shù)谝淮嗡阉鞯絊[5]和T[5]不等后，S下標(biāo)不是回溯到1，T下標(biāo)也不是回溯到開始，而是根據(jù)T中T[5]==’d’的模式函數(shù)值（next[5]=2），直接比較S[5]和T[2]是否相等，因?yàn)橄嗟龋琒和T的下標(biāo)同時(shí)增加；因?yàn)橛窒嗟?，S和T的下標(biāo)又同時(shí)增加…最終在S中找到了T。KMP匹配算法和簡(jiǎn)單匹配算法效率比較，一個(gè)極端的例子是：在S=“AAAAAA…AAB“(100個(gè)A)中查找T=”AAAAAAAAAB”,簡(jiǎn)單匹配算法每次都是比較到T的結(jié)尾，發(fā)現(xiàn)字符不同，然后T的下標(biāo)回溯到開始，S的下標(biāo)也要回溯相同長(zhǎng)度后增1，繼續(xù)比較。如果使用KMP匹配算法，就不必回溯。時(shí)間復(fù)雜度從O(m*n)降為O(m+n)。KMP算法的核心思想：

利用已經(jīng)得到的部分匹配信息來(lái)進(jìn)行后面的匹配過(guò)程。

T[5]==’d’的模式函數(shù)值等于2,即(next[5]=2)表示T[5]==’d’的前面有2個(gè)字符和開始的兩個(gè)字符相同，且T[5]==’d’不等于開始的兩個(gè)字符之后的第三個(gè)字符(T[2]=’c’)。如果開始的兩個(gè)字符之后的第三個(gè)字符也為’d’,那么，盡管T[5]==’d’的前面有2個(gè)字符和開始的兩個(gè)字符相同，T[5]==’d’的模式函數(shù)值也不為2，而是為0。next函數(shù)：(1)next[0]=-1，任何串的第一個(gè)字符的模式值規(guī)定為-1(2)next[j]=-1，模式串t中下標(biāo)為j的字符，如果與首字符相同，且j的前面的

1—k個(gè)字符與開頭的1..k個(gè)字符不等(或者相等但t[k]==t[j]),1≤k<j

如：t=”abCabCad”則next[6]=-1，因t[3]=t[6](3)next[j]=k，模式串t中下標(biāo)為j的字符，如果j的前面k個(gè)字符與開頭的k個(gè)字符相等，且tj

≠tk,1≤k<j，即“t0t1t2…,…,tk-1”=“tj-ktj-k+1tj-k+2…tj-1”

且tj

≠tk，1≤k<j(4)next[j]=0，除(1)、(2)、(3)的其他情況。例1、求T=“abcac”的模式函數(shù)的值

next[0]=-1根據(jù)(1)next[1]=0根據(jù)(4)因（3）有1<=k<j;不能說(shuō)，j=1,T[j-1]==T[0]next[2]=0根據(jù)(4)因（3）有1<=k<j;（T[0]=a）!=（T[1]=b）

next[3]=-1根據(jù)(2)next[4]=1根據(jù)(3)T[0]=T[3]且T[1]=T[4]若T=“abcab”為什么T[0]==T[3],還會(huì)有next[4]=0?因?yàn)門[1]==T[4]根據(jù)(3)”且T[j]!=T[k]”被劃入(4)。下標(biāo)01234Tabcacnext-100-11下標(biāo)01234Tabcabnext-100-10例2、求T=”ababcaabc”的模式函數(shù)的值

next[0]=-1根據(jù)(1)next[1]=0根據(jù)(4)next[2]=-1根據(jù)(2)next[3]=0根據(jù)(3)雖T[0]=T[2]但T[1]=T[3]被劃入(4)next[4]=2根據(jù)(3)T[0]T[1]=T[2]T[3]且T[2]!=T[4]next[5]=-1根據(jù)(2)next[6]=1根據(jù)(3)T[0]=T[5]且T[1]!=T[6]next[7]=0根據(jù)(3)雖T[0]=T[6]但T[1]=T[7]被劃入(4)next[8]=2根據(jù)(3)T[0]T[1]=T[6]T[7]且T[2]!=T[8]

即：下標(biāo)012345678Tababcaabcnext-10-102-1102next[3]=0，而不是=1；next[6]=1，而不是=-1；next[8]=2，而不是=0；例3、求T=”abCabCad”的模式函數(shù)的值下標(biāo)01234567TabCabCadnext-100-100-14next[5]=0根據(jù)(3)雖T[0]T[1]=T[3]T[4]，但T[2]==T[5]next[6]=-1根據(jù)(2)雖前面有abC=abC，但T[3]==T[6]next[7]=4根據(jù)(3)前面有abCa=abCa，且T[4]!=T[7]若T[4]==T[7]，即T=”adCadCad”，則

next[7]=0,而不是=4，因?yàn)門[4]==T[7]下標(biāo)01234567TabCabCadnext-100-100-10next函數(shù)值究竟是什么含義？設(shè)在字符串S中查找模式串T，若S[m]!=T[n]，那么，取T[n]的模式函數(shù)值next[n]1、next[n]=-1表示S[m]和T[0]間接比較過(guò)了，不相等，下一次比較S[m+1]和T[0]；2、next[n]=0表示比較過(guò)程中產(chǎn)生了不相等，下一次比較S[m]和T[0]；3、next[n]=k>0但k<n，表示S[m]的前k個(gè)字符與T中的，開始k個(gè)字符已經(jīng)間接比較相等了，下一次比較S[m]和T[k]相等嗎？4、其他值。voidget_next(constchar*T,intnext[]){//求模式串T的next函數(shù)值并存入數(shù)組nextintj=0,k=-1;next[0]=-1;while(T[j]!='\0'){if(k==-1||T[j]==T[k]){++j;++k;if(T[j]!=T[k])next[j]=k;elsenext[j]=next[k];}//ifelsek=next[k];}//while}//get_next

求串T的模式值next[n]的函數(shù)//get_next函數(shù)的另一種寫法voidget_next_1(char*t,intnext[]){intj=0,k=-1;next[0]=-1;while(t[j]!='\0'){if(k!=-1&&t[k]!=t[j])k=next[k];++j;++k;if(t[k]==t[j])next[j]=next[k];elsenext[j]=k;}}intKMP(char*s,char*t,intnext[]){intindex=0,i=0,j=0