【文章內(nèi)容簡(jiǎn)介】 p=pnext。 } rnext=NULL。 return str。 } (10) DispStr(s) 輸出串 s的所有元素值 。 void DispStr(LiString *s) { LiString *p=snext。 while (p!=NULL) { printf(%c,pdata)。 p=pnext。 } printf(\n)。 } 例 在鏈串中 ,設(shè)計(jì)一個(gè)算法把最先出現(xiàn)的子串 ab改為 xyz。 解 :在串 s中找到最先出現(xiàn)的子串 ab,p指向 data域值為 39。a39。的結(jié)點(diǎn) ,其后為 data域值為 39。b39。的結(jié)點(diǎn) 。 將它們的 data域值分別改為 39。x39。和 39。z39。,再創(chuàng)建一個(gè) data域值為 39。y39。的結(jié)點(diǎn) ,將其插入到 *p之后 。 本例算法如下 : void Repl(LiString *amp。s) { LiString *p=snext,*q。int find=0。 while (pnext!=NULL amp。amp。 find==0) { if (pdata==?a? amp。amp。 pnextdata==?b?) /*找到 */ { pdata=39。x39。pnextdata=39。z39。 /*替換為 xyz*/ q=(lstring *)malloc(sizeof(lstring))。 qdata=39。y39。qnext=pnext。 pnext=q。 find=1。 } else p=pnext。 } } 串的模式匹配 設(shè)有主串 s和子串 t,子串 t的定位就是要在主串 s中找到一個(gè)與子串 t相等的子串。通常把主串 s稱為目標(biāo)串 ,把子串 t稱為 模式串 ,因此定位也稱作模式匹配。模式匹配成功是指在目標(biāo)串 s中找到一個(gè)模式串 t；不成功則指目標(biāo)串 s中不存在模式串 t。 BruteForce算法 BruteForce簡(jiǎn)稱為 BF算法 ,亦稱簡(jiǎn)單匹配算法 ,其基本思路是 : 從目標(biāo)串 s=s0s1…s n1的第一個(gè)字符開始和模式串 t=t0t1…t m1中的第一個(gè)字符比較 ,若相等 ,則繼續(xù)逐個(gè)比較后續(xù)字符；否則從目標(biāo)串 s的第二個(gè)字符開始重新與模式串 t的第一個(gè)字符進(jìn)行比較。依次類推 ,若從模式串 s的第 i個(gè)字符開始 ,每個(gè)字符依次和目標(biāo)串 t中的對(duì)應(yīng)字符相等 ,則匹配成功 ,該算法返回 i；否則 ,匹配失敗 ,函數(shù)返回 1。 int indexpos(SqString str,SqString substr) { int i,j,k,idx=1。 for (i=0。i。i++) { for (j=i,k=0。[j]==[k]。j++,k++)。 if (k==) //注意 j每次從 i開始 ,有回溯 return(i)。 } return(1)。 } 算法 1 int index(SqString s,SqString t) { int i=0,j=0,k。 while (i amp。amp。 j) { if ([i]==[j]) /*繼續(xù)匹配下一個(gè)字符 */ { i++。 j++。 } /*主串和子串依次匹配下一個(gè)字符 */ else /*主串 、 子串指針回溯重新開始下一次匹配 */ { i=ij+1。 /*主串從下一個(gè)位置開始匹配 */ j=0。 /*子串從頭開始匹配 */ } } if (j=) k=。 /*返回匹配的第一個(gè)字符的下標(biāo) */ else k=1。 /*模式匹配不成功 */ return k。 } 算法 2 這個(gè)算法簡(jiǎn)單 ,易于理解 ,但效率不高 ,主要原因是 :主串指針 i在若干個(gè)字符序列比較相等后 ,若有一個(gè)字符比較不相等 ,仍需回溯 (即 i=ij+1)。該算法在最好情況下的時(shí)間復(fù)雜度為 O(m),即主串的前 m個(gè)字符正好等于模式串的 m個(gè)字符。在最壞情況下的時(shí)間復(fù)雜度為 O(n*m)。 例如 ,設(shè)目標(biāo)串 s=“cddcdc”,模式串 t=“cdc”。 s的長(zhǎng)度為 n(n=6),t的長(zhǎng)度為 m(m=3)。用指針 i指示目標(biāo)串 s的當(dāng)前比較字符位置 ,用指針 j指示模式串 t的當(dāng)前比較字符位置。 BF模式匹配過程如下所示。 第 1 次匹配 s = c d d c d c i=2 t = c d c j=2 失敗 第 2 次匹配 s = c d d c d c i=1 t = c d c j=0 失敗 第 3 次匹配 s = c d d c d c i=2 t = c d c j=0 失敗 第 4 次匹配 s = c d d c d c i=5 t = c d c j=2 成功 KMP算法 KMP算法是 、 共同提出的 ,簡(jiǎn)稱 KMP算法。該算法較 BF算法有較大改進(jìn) ,主要是消除了主串指針的回溯 ,從而使算法效率有了某種程度的提高。 所謂 真子串 是指模式串 t存在某個(gè) k(0＜ k＜ j)， 使得 t0t1… tk = tjktjk+1… tj 成立 。 例如 ， t= abab, 即 t0t1＝ t2t3 也就是說 ， “ ab”是真子串 。 真子串就是模式串中隱藏的信息 ， 利用它來提高模式匹配的效率 。 一般情況 :設(shè)主串 s=s0s1… sn1,模式 t=t0t1… tm1,在進(jìn)行第 i趟匹配時(shí) ， 出現(xiàn)以下情況： 這時(shí)，應(yīng)有 t0t1… tj1=sijsij+1… si1 () 如果在模式 t中 ， t0t1… tj1≠t1t2… tj () s ： s 0 s 1 … s i j s i j+1 … s i 1 s i s i + 1 … s n 1 t ： t 0 t 1 … t j 1 t j t j+1 … s m 1 則回溯到 sij+1開始與 t匹配 ， 必然 “ 失配 ” ， 理由很簡(jiǎn)單：由 ()式和 ()式綜合可知： t0t1… tj1≠sij+1sij+2… si 既然如此 ， 回溯到 sij+1開始與 t匹配可以不做 。 那么 ， 回溯到 sij+2開始與 t匹配又怎么樣 ？ 從上面推理可知 ， 如果 t0t1… tj2≠t2t3… tj 仍然有 t0t1… tj2≠sij+2sij+3… si 這樣的比較仍然 “ 失配 ” 。 依此類推 ， 直到對(duì)于某一個(gè)值 k， 使得： t0t1… tk2≠ tjk+1tjk+2… tj1 且 t0t1… tk1=tjktjk+1… tj1“ 才有 tjktjk+1… tj1=siksik+1… si1=t0t1… tk1 說明下一次可直接比較 si和 tk，這樣，我們可以直接把第 i趟比較“失配”時(shí)的模式 t從當(dāng)前位置直接右滑 jk位。而這里的 k即為 next[j]。 s ： s 0 s 1 … s i j s i j +1 … s i k s i k +1 … s i 1 s i s i+1 … s n 1 t ： t 0 t 1 … t k 1 t k … t j 1 t j t j +1 … s m 1 s ： s 0 s 1 … s i j s i j +1 … s i k s i k +1 … s i 1 s i s i+1 … s n 1 t ： t 0 t 1 … t k 1 t k … t j 1 t j t j +1 … s m 1 t 右滑 j k 位 例如 t=abab,由于 t0t1 =t2t3(這里 k=1,j=3),則存在真子串 。 設(shè) s=abacabab,t=abab,第一次匹配過程如下所示 。 第 1 次匹配 s = a b a c a b a b i= 3 t = a b a b j= 3 失敗 此時(shí)不必從 i=1(i=ij+1=1),j=0重新開始第二次匹配。因 t0≠t1,s1=t1,必有 s1≠t0,又因 t0 =t2,s2=t2,所以必有s2=t0。因此 ,第二次匹配可直接從 i=3,j=1開始。 為此 ,定義 next[j]函數(shù)如下 : max{k|0kj,且 “ t0t1… tk1”=“tjktjk+1… tj1” } 當(dāng)此集合非空時(shí) 1 當(dāng) j=0時(shí) 0 其他情況 next[j]= j 0 1 2 3 t[j] a b a b next[j] 1 0 0 1 t=“abab”對(duì)應(yīng)的 next數(shù)組如下 : void GetNext(SqString t,int next[]) { int j,k。 j=0。k=1。next[0]=1。 while (j) { if (k==1 || [j]==[k]) /*k為 1或比較的字符相等時(shí) */ { j++。k++。 next[j]=k。 } else k=next[k]。 } } 由模式串 t求出 next值的算法 int KMPIndex(SqString s,SqString t) { int next[MaxSize],i=0,j=0,v。 GetNext(t,next)。 while (i amp。amp。 j) { if (j==1 || [i]==[j]) { i++。j++。 } /*i,j各增 1*/ else j=next[j]。 /*i不變 ,j后退 */ } if (j=) v=。 /*返回匹配模式串的首字符下標(biāo) */ else v=1。 /*返回不匹配標(biāo)志 */ return v。 } KMP算法 設(shè)主串 s的長(zhǎng)度為 n,子串 t長(zhǎng)度為 m。 在 KMP算法中求 next數(shù)組的時(shí)間復(fù)雜度為O(m),在后面的匹配中因主串 s的下標(biāo)不減即不回溯 ,比較次數(shù)可記為 n,所以 KMP算法總的時(shí)間復(fù)雜度為O(n+m)。 例如 ,設(shè)目標(biāo)串 s=“aaabaaaab”,模式串 t=“aaaab”。s的長(zhǎng)度為 n(n=9),t的長(zhǎng)度為 m(m=5)。用指針 i指示目標(biāo)串 s的當(dāng)前比較字符位置 ,用指針 j指示模式串 t的當(dāng)前比較字符位置。 KMP模式匹配過程如下所示。 第 1 次匹配 s = a a a ba a a ab i=3 t = aaaab j= 3 , j= n e x t[3 ]= 2 失敗 第 2 次匹配 s = a a