【正文】 //i指向S中第一個(gè)比較字符，j指向T中第一個(gè)字符 int m=Length_SS(T), n=Length_SS(S)。而用KMP算法的比較過(guò)程為：(1) 比較5次后滑動(dòng)模式T:j=next[4]=0,即向右滑動(dòng)4個(gè)字符，此時(shí)j=0,i=4；(2) 再次連續(xù)比較5次后將模式T向右滑動(dòng)4個(gè)字符，此時(shí)j=0,i=9；以此類(lèi)推，共需要比較的次數(shù)為54=20次（）。從以上分析的比較過(guò)程可知，總的比較次數(shù)為：7+2(527)+1=98次（）再如：主串為S=“abcdabcdabcdabcde”，模式串為T(mén)=“abcde”,則next={1,0,0,0,0}。(5) 重復(fù)(2)、(3)、(4)的步驟527=45次后，i、j均指向最后的字符‘b’,即S[i]=T[j]。(3) 比較S[i]和T[j]，均為‘a(chǎn)’相同，i++,j++。(1) 連續(xù)比較8次時(shí)，i=7,j=7，此時(shí)分別指向S的第8個(gè)‘a(chǎn)’和T中最后的‘b’；即S[i]≠T[j]。 }}運(yùn)行結(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模式匹配算法的比較過(guò)程假設(shè)主串為S=“aaaaaa……aaaaab”（其中共有52個(gè)‘a(chǎn)’和1個(gè)‘b’），模式串為T(mén)=“aaaaaaab”（其中共有7個(gè)‘a(chǎn)’和1個(gè)‘b’）。j++)coutnext[j] 。 //計(jì)算模式串p[i]的next數(shù)組 for(j=0。i6。 int next[50],i,j。 else k=next[k]。 while(T[n])n++。計(jì)算next數(shù)組的算法void GetNext(char* T,int* next)用C++語(yǔ)言實(shí)現(xiàn)如下void GetNext(char* T,int* next){ int i=0,k=1,n=0。next數(shù)組定義為：其中next[j]=k表明，存在整數(shù)k滿足條件0kj，并且在模式T中存在下列關(guān)系：“T[0]T[1]…T[k1]”=“T[jk]T[jk+1]…T[j1]”，而對(duì)任意的整數(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ù)組的算法實(shí)現(xiàn)由定義可知，next[0]=1,next[1]=0，假設(shè)現(xiàn)已求得next[0],next[1], …,next[j],那么可以采用以下遞推的方法求出next[j+1]。1．模式的next數(shù)組模式匹配的KMP算法是，每當(dāng)一趟匹配比較過(guò)程中出現(xiàn)字符不相同的情況時(shí)，不需要回溯指針i,而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式T向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，再繼續(xù)進(jìn)行比較。,，稱(chēng)之為克努特莫里斯普拉特操作，簡(jiǎn)稱(chēng)KMP算法，他是一種改進(jìn)的模式匹配算法。初始位置指針i一共要回溯527=45次，總的比較次數(shù)為：8(45+1)=368次。例如：S=“aaaaaa……aaaaab”共有52個(gè)‘a(chǎn)’和1個(gè)‘b’,T=“aaaaaaab”共有7個(gè)‘a(chǎn)’和1個(gè)‘b’。 //若匹配不成功，則返回0}算法分析：在一般情況下，BF算法的時(shí)間復(fù)雜度為O(m+n)，其中m,n分別為串S和T的長(zhǎng)度。} //若不相等，則重新開(kāi)始新一輪比較 } if(!T[j]) return(i+1)。 //若字符相等，則繼續(xù)比較后續(xù)字符 else {i++。amp。if(i0||pos+Length_SS(T)Length_SS(S)+1) return(0)。以此類(lèi)推，直至模式T中的每個(gè)字符依次和主串S中的一個(gè)連續(xù)的字符序列相等，則稱(chēng)匹配成功，函數(shù)返回T的第一個(gè)字符在S中的位置，否則匹配不成功，函數(shù)返回0值。在串的模式匹配算法中，最簡(jiǎn)單、最直觀的算法是BF（BruteForce,布魯特福斯）算法，在該算法中，分別利用指針i和指針j指示主串S和模式T中當(dāng)前正待比較的字符下標(biāo)。如果匹配成功，函數(shù)返回T在S中第pos個(gè)字符以后的串值中第一次出現(xiàn)的開(kāi)始位置；否則函數(shù)返回0值。模式匹配是各種串處理系統(tǒng)中最重要的操作之一。其中，串S稱(chēng)為主串，串T稱(chēng)為模式。因此，串的塊鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不如定長(zhǎng)順序存儲(chǔ)和堆分配存儲(chǔ)結(jié)構(gòu)靈活，它占用存儲(chǔ)空間大且操作復(fù)雜。4．塊鏈?zhǔn)酱鎯?chǔ)表示的特點(diǎn)在一般情況下，對(duì)以塊鏈?zhǔn)酱鎯?chǔ)表示的串進(jìn)行操作時(shí)比較麻煩，比如在串中插入一個(gè)子串時(shí)可能需要分割結(jié)點(diǎn)，連接兩個(gè)串時(shí)，如果第一個(gè)串的最后一個(gè)結(jié)點(diǎn)沒(méi)有填滿，還需要添加其它字符。為了便于研究串值的存儲(chǔ)效率我們給出如下存儲(chǔ)密度的計(jì)算公式：假定next指針變量占用4個(gè)字節(jié)，每個(gè)字符占用1個(gè)字節(jié)，每個(gè)塊中存放m個(gè)字符，那么串值的存儲(chǔ)密度可以表示為ρ=m/(m+4)。3．塊鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)密度在串的塊鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)大小的選擇很重要，它直接影響到串處理操作的效率。 //塊鏈?zhǔn)浇Y(jié)構(gòu)的類(lèi)型定義在一般情況下，對(duì)串的操作只需要從前向后掃描即可，故對(duì)串值不必建立雙向鏈表。 //串的頭指針和尾指針 int curlen。 //指向下一個(gè)結(jié)點(diǎn)的指針}。2．塊鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的表示在C++運(yùn)行環(huán)境中，可將塊鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示如下：define CHUNKSIZE 80 //定義每個(gè)結(jié)點(diǎn)的大小struct Chunk{ char ch[CHUNKSIZE]。為了便于進(jìn)行串的操作，當(dāng)以鏈表存儲(chǔ)串值時(shí)，除了頭指針head外還可以附設(shè)一個(gè)指向尾結(jié)點(diǎn)的指針tail，并給出當(dāng)前串的長(zhǎng)度。對(duì)于串“abcdefghijk”，如果采用每個(gè)結(jié)點(diǎn)存放一個(gè)字符的鏈表結(jié)構(gòu)存儲(chǔ)，(a)所示；如果采用每個(gè)結(jié)點(diǎn)存放三個(gè)字符的鏈表結(jié)構(gòu)存儲(chǔ)，(b)所示。1．塊鏈?zhǔn)酱鎯?chǔ)的概念和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類(lèi)似，可以采用鏈表方式存儲(chǔ)串。 else cout位置不對(duì)!\n。 StrAssign_HS(T,ss1)。 cout輸入替換串T:\n。 cinposlen。 else cout位置不對(duì)!\n。 StrAssign_HS(V,ss1)。 cout輸入要插入的子串V:\n。 cinpos。 else cout位置不對(duì)!\n。 cinposlen。 coutlength=Length_HS(S)endl。 Concat_HS(S,S1,S2)。 else if(n0)coutS1S2\n。 n=StrComp_HS(S1,S2)。coutlen2=Length_HS(S2)endl。 StrAssign_HS(S2,ss2)。 (ss2,sizeof(ss2))。 while(1) { cout(1)串初始化操作：\n輸入兩個(gè)字符串:\n。 SString ss1,ss2。 return(1)。 //取S中剩余的部分 delete[]。j++)[i++]=[j]。 //取S中前面的部分 for(j=0。in1。 =new char[+1]。 if(n1||m0||n+m+1)return(0)。S,int n,int m,HString T){ int i,j,k=n+m1。S,int n,int m,HString T)該操作將串S中第n個(gè)字符開(kāi)始的m個(gè)字符替換為串T，如果位置n和字符數(shù)m合理返回1否則返回0。 return 1。 //取S中剩余的內(nèi)容 delete[]。j++)[i++]=[j]。 for(j=0。i++)[i]=[i]。 //重新分配空間 for(i=0。 //位置不合理返回0值 =+。 HString S1。int StrInsert_HS(HString amp。}（7）串插入操作的算法int StrInsert_HS(HString amp。 //將子串復(fù)制到Sub中 [i]=0。ilen。 //動(dòng)態(tài)分配子串的存儲(chǔ)空間 =len。 if(pos1||len1||pos+len+1) return(0)。int SubString_HS(HString amp。 //將S2連接到T的末尾}（6）求子串的算法int SubString_HS(HString amp。 //將S1復(fù)制到T i。 =new char[+1]。 =+。void Concat_HS(HString amp。 }}（5）串的連接操作void Concat_HS(HString amp。 =NULL。void ClearString_HS(HString amp。 }（4）串的清空操作void ClearString_HS(HString amp。i++) if([i]!=[i])break。amp。 for(i=0。 }（3）串的比較操作int StrComp_HS(HString S,HString T)該操作比較串S、T的大小。 // }}（2）求串長(zhǎng)的操作int Length_HS(HString S)該操作返回串S的長(zhǎng)度，如果S為空串則返回0。[i]=str[i]。 //對(duì)空串進(jìn)行初始化 else { =new char[len+1]。 //計(jì)算串的長(zhǎng)度 =len。T,char str[]){ int len=0,i。T,char str[])該操作由字符串常量str生成一個(gè)HString型串T。 //串的長(zhǎng)度}。1．串的堆分配存儲(chǔ)結(jié)構(gòu)在C++運(yùn)行環(huán)境中，堆分配存儲(chǔ)結(jié)構(gòu)定義為struct HString{ char *ch。因此，事先為串變量設(shè)置固定大小空間的數(shù)組不盡合理。 }}（程序運(yùn)行過(guò)程略）3．定長(zhǎng)順序存儲(chǔ)的特點(diǎn)對(duì)于定長(zhǎng)順序存儲(chǔ)的串在基本操作方面主要有以下特點(diǎn)：（1）對(duì)于求串長(zhǎng)度和串的復(fù)制操作而言，其時(shí)間復(fù)雜度依賴(lài)于字符串的長(zhǎng)度；（2）在串刪除和串插入操作時(shí)必須移動(dòng)大量的字符；（3）如果在串輸入、串連接、串插入和串替換操作中串值的長(zhǎng)度超過(guò)MAXLEN，則按約定采取“截尾”法處理，這將導(dǎo)致操作結(jié)果的不合理。 if(Replace_SS(s3,pos,len,T)) cout替換結(jié)果為:\ns3=s3endl。 (str1,sizeof(str1))。 cout輸入替換串:\n。 cout(6)串替換操作：\n輸入替換的位置和字符數(shù)(pos len):。 if(SubString_SS(sub,s3,pos,len)) coutsub=subendl。cout(5)求子串操作：\n輸入開(kāi)始位置和串長(zhǎng)(pos len):\n。 l3=Length_