【文章內(nèi)容簡介】 int curlen。 //串的長度}。 //塊鏈式結(jié)構(gòu)的類型定義在一般情況下，對串的操作只需要從前向后掃描即可，故對串值不必建立雙向鏈表。設(shè)尾指針的目的是為了便于進行串的連接操作，在串連接時需要處理第一個串尾結(jié)點中的無效字符。3．塊鏈式存儲的存儲密度在串的塊鏈式存儲結(jié)構(gòu)中，結(jié)點大小的選擇很重要，它直接影響到串處理操作的效率。如果塊選取的充分大時（可在一個塊中存儲串的所有字符）即為定長存儲；如果每個塊只放一個字符時即為鏈表存儲。為了便于研究串值的存儲效率我們給出如下存儲密度的計算公式：假定next指針變量占用4個字節(jié)，每個字符占用1個字節(jié)，每個塊中存放m個字符，那么串值的存儲密度可以表示為ρ=m/(m+4)。顯然，存儲密度小（比如每個塊存放1個字符時ρ=20%），運算處理方便，但是存儲占用量大；存儲密度大（比如每個塊存放80個字符時ρ=20/21=95%），雖然存儲占用量小，但是串值的運算處理（比如串的插入、刪除、連接和替換等操作）不太方便。4．塊鏈式存儲表示的特點在一般情況下，對以塊鏈式存儲表示的串進行操作時比較麻煩，比如在串中插入一個子串時可能需要分割結(jié)點，連接兩個串時，如果第一個串的最后一個結(jié)點沒有填滿，還需要添加其它字符。總的來說，用鏈表作為串的存儲方式是不太實用的。因此，串的塊鏈式存儲結(jié)構(gòu)不如定長順序存儲和堆分配存儲結(jié)構(gòu)靈活，它占用存儲空間大且操作復(fù)雜。設(shè)S和T是兩個給定的串，在串S中尋找串值等于T的子串的過程稱為模式匹配。其中，串S稱為主串，串T稱為模式。如果在串S中找到等于串T的子串，則稱匹配成功；否則匹配失敗。模式匹配是各種串處理系統(tǒng)中最重要的操作之一。模式匹配的操作記為Index(S,T,pos)，該函數(shù)的功能是，從串S的第pos個字符開始的字符序列中查找值等于T的子字符串。如果匹配成功，函數(shù)返回T在S中第pos個字符以后的串值中第一次出現(xiàn)的開始位置；否則函數(shù)返回0值。顯然這里隱含要求模式串T不能為空串。在串的模式匹配算法中，最簡單、最直觀的算法是BF（BruteForce,布魯特福斯）算法，在該算法中，分別利用指針i和指針j指示主串S和模式T中當前正待比較的字符下標。算法的基本思想是：從主串S的第pos個字符起和模式T的第一個字符比較，若相等，則繼續(xù)逐個比較后面的字符；否則從主串S的下一個字符起再重新和模式T的第一個字符開始逐個比較。以此類推，直至模式T中的每個字符依次和主串S中的一個連續(xù)的字符序列相等，則稱匹配成功，函數(shù)返回T的第一個字符在S中的位置，否則匹配不成功，函數(shù)返回0值。BF算法表示的串查找函數(shù)int IndexBF_SS(SString S,SString T,int pos)的C++語言表示為：int IndexBF_SS(SString S,SString T,int pos=1){//求子串T在S中從pos個位置開始首次出現(xiàn)的位置 int i=pos1,j=0。if(i0||pos+Length_SS(T)Length_SS(S)+1) return(0)。 while(S[i+j]amp。amp。T[j]) { if(S[i+j]==T[j])j++。 //若字符相等，則繼續(xù)比較后續(xù)字符 else {i++。 j=0。} //若不相等，則重新開始新一輪比較 } if(!T[j]) return(i+1)。 //若匹配成功，則返回T首次出現(xiàn)的開始位置 else return(0)。 //若匹配不成功，則返回0}算法分析：在一般情況下，BF算法的時間復(fù)雜度為O(m+n)，其中m,n分別為串S和T的長度。但是在有些情況下，該算法的效率很低。例如：S=“aaaaaa……aaaaab”共有52個‘a(chǎn)’和1個‘b’,T=“aaaaaaab”共有7個‘a(chǎn)’和1個‘b’。由于每趟比較都是在最后一個字符出現(xiàn)不相等，此時需要將初始位置指針i回溯到i+1的位置上，并從模式的第一個字符開始重新比較。，初始位置指針i一共要回溯527=45次，總的比較次數(shù)為：8(45+1)=368次。所以，在最壞的情況下BF算法的時間復(fù)雜度為O(mn)。,，稱之為克努特莫里斯普拉特操作，簡稱KMP算法，他是一種改進的模式匹配算法。此算法可使時間復(fù)雜度在O(m+n)的數(shù)量級上完成串的模式匹配操作。1．模式的next數(shù)組模式匹配的KMP算法是，每當一趟匹配比較過程中出現(xiàn)字符不相同的情況時，不需要回溯指針i,而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式T向右“滑動”盡可能遠的一段距離后，再繼續(xù)進行比較。為此需要引入一個有關(guān)模式串T的整型數(shù)組next，其中第j個元素next[j1]表示當模式串T中的第j個字符與主串S中相應(yīng)字符匹配失敗時，在模式T中需要重新和主串S中該字符進行比較的字符的下標值。next數(shù)組定義為：其中next[j]=k表明，存在整數(shù)k滿足條件0kj，并且在模式T中存在下列關(guān)系：“T[0]T[1]…T[k1]”=“T[jk]T[jk+1]…T[j1]”，而對任意的整數(shù)k1(0kk1j)都有：“T[0]T[1]…T[k11]”≠“T[jk1]T[jk1+1]…T[j1]”例如：（1）模式T=“aaaaaaab”的next數(shù)組為next={1,0,1,2,3,4,5,6}（2）模式T=“abaabcac”的next數(shù)組為next={1,0,0,1,1,2,0,1}（3）模式T=“ababcabcacbab”的next數(shù)組為next={1,0,0,1,2,0,1,2,0,1,0,0,1}2．next數(shù)組的算法實現(xiàn)由定義可知，next[0]=1,next[1]=0，假設(shè)現(xiàn)已求得next[0],next[1], …,next[j],那么可以采用以下遞推的方法求出next[j+1]。令k=next[j]，（1）如果k=1或T[j]=T[k],則轉(zhuǎn)入步驟(3)（2）取k=next[k],再重復(fù)操作(1)、(2)（3）next[j+1]=k+1。計算next數(shù)組的算法void GetNext(char* T,int* next)用C++語言實現(xiàn)如下void GetNext(char* T,int* next){ int i=0,k=1,n=0。 next[0]=1。 while(T[n])n++。 //計算模式串T的長度n while(in1) { if(k==1||T[i]==T[k]) next[++i]=++k。 else k=next[k]。 }}void main(){ char p[6][50]={ababcabcacbab,abaabcac,aaabcaab,abcabca,babbabab,abcaabbabcabaac}。 int next[50],i,j。 for(i=0。i6。i++) { GetNext(p[i],next)。 //計算模式串p[i]的next數(shù)組 for(j=0。p[i][j]。j++)coutnext[j] 。 //顯示輸出p[i]的next數(shù)組 coutendl。 }}運行結(jié)果為：1 0 0 1 2 0 1 2 0 1 0 0 11 0 0 1 1 2 0 11 0 1 2 0 0 1 21 0 0 0 1 2 31 0 0 1 1 2 3 21 0 0 0 1 1 2 0 1 2 3 4 2 1 13．KMP模式匹配算法的比較過程假設(shè)主串為S=“aaaaaa……aaaaab”（其中共有52個‘a(chǎn)’和1個‘b’），模式串為T=“aaaaaaab”（其中共有7個‘a(chǎn)’和1個‘b’）。下面給出KMP模式匹配算法的比較過程：首先求得模式T的next數(shù)組為next[]={1,0,1,2,3,4,5,6}，主串與模式串的字符下標初值為i=0,j=0。(1) 連續(xù)比較8次時，i=7,j=7，此時分別指向S的第8個‘a(chǎn)’和T中最后的‘b’；即S[i]≠T[j]。 (2) 取j為next[j]=next[7]的值6，即j=6指向T中第7個‘a(chǎn)’(表示模式T向后滑動76=1個字符)。(3) 比較S[i]和T[j]，均為‘a(chǎn)’相同，i++,j++。(4) 此時i的值+1,j=7，分別指向S的下一個‘a(chǎn)’和T中最后的‘b’；即S[i]≠T[j]，轉(zhuǎn)入（2）繼續(xù)。(5) 重復(fù)(2)、(3)、(4)的步驟527=45次后，i、j均指向最后的字符‘b’,即S[i]=T[j]。(6) i++,j++操作后j=m(m為T的長度8)，循環(huán)結(jié)束，返回im+1。從以上分析的比較過程可知，總的比較次數(shù)為：7+2(527)+1=98次（）再如：主串為S=“abcdabcdabcdabcde”，模式串為T=“abcde”,則next={1,0,0,0,0}。那么，可以算出用BF算法時的比較次數(shù)為29次。而用KMP算法的比較過程為：(1) 比較5次后滑動模式T:j=next[4]=0,即向右滑動4個字符，此時j=0,i=4；(2) 再次連續(xù)比較5次后將模式T向右滑動4個字符，此時j=0,i=9；以此類推，共需要比較的次數(shù)為54=20次（）。4．KMP模式匹配算法的實現(xiàn)KMP模式匹配算法int Index_KMP(SString S,SString T,int pos)的C++語言實現(xiàn)int Index_KMP(SString S,SString T,int pos=1){ int i=pos1,j=0。 //i指向S中第一個比較字符，j指向T中第一個字符 int m=Length_SS(T), n=Length_SS(S)。 int *next=new int[m]。 //定義模式T的next數(shù)組 if(i0||pos+mn+1) return 0。 //位置不合理返回0值 GetNext(T,next)。 //計算next while(inamp。amp。jm) { if(j==1||S[i]==T[j]){j++。i++。} //比較后繼字符 else j=next[j]。 //回溯模式指針j } if(j=m) return(im+1)。 //匹配成功 else return(0)。}void main(){ SString S,T。 int pos,n。 cout輸入主串S:\n。 cinS。 cout輸入子串T:\n。 cinT。 cout輸入位置pos:\n。cinpos。 if(n=Index_KMP(S,T,pos)) cout首次匹配地址為:nendl。 else cout匹配不成功!\n。}【】編寫程序，分別計算模式匹配過程中，BF算法和KMP算法的字符比較次數(shù)。（1）函數(shù)int IndexBF(SString S,SString T,intamp。 num)的功能是通過BF算法返回串T在S中首次出現(xiàn)的位置，參數(shù)num表示匹配過程中元素的比較次數(shù)。int IndexBF(SString S,SString T,intamp。 num){ int i=0,j=0。 num=0。 if(Length_SS(T)Length_SS(S)) return(0)。 while(S[i+j]amp。amp。T[j])