數(shù)據(jù)結(jié)構(gòu)串ppt課件-資料下載頁
2024-11-03 22:17本頁面
【正文】 算法 KMP的模式匹配算法。 int index_kmp(char s[],char t[],int next[]) /* 從主串 s起始位置開始查找 */ { int i=0, j=0, m, n。 m=strlen(s)。 n=strlen(t)。 while(im amp。amp。 jn) if(j==1||s[i]==t[j]) { i++。 j++。 } else /* t[j]失配于 s[i] */ j=next[j]。 /* 回溯到 next[j],再與 s[i]比較 */ if(j=n) return(in)。 else return(1)。 } ? 求 next[]的算法又是如何實現(xiàn)的？ ? 由定義可知： next[0]=1 設(shè) next[j]=k，這表明在模式串中 ? ″t0t1…tk 1”=”tjktjk+1…tj 1″ 其中 k為滿足 0kj的某個值，并且不可能存在 k’k滿足上式。此時 next[j+1]=?可能有兩種情況： (1)若 tk=tj，則表明在模式串中 ″t0t1…tk 1tk″=″tjktjk+1…tj 1tj″ 并且，不可能存在 k’k滿足上式，這就是說next[j+1]=k+1，即 next[j+1]=next[j]+1 (2)若 tk!=tj，則表明在模式串中 ″t0t1…tk 1tk″!= ″tjktjk+1…tj 1tj″ 此時可以把求 next[]數(shù)組問題看成是一個模式匹配問題，整個模式串既是主串又是模式串，而當(dāng)前在匹配過程中，已有 t0=tjk ， t1=tjk+1， … ， tk1=tj1，則當(dāng) tk!=tj時應(yīng)將模式串向右滑動以至于使模式串中第 k’=next[k]個字符和主串中的第 j個字符比較，若 tk’ =tj ，則說明在主串中第 j+1個字符前存在一個長度為 k’+1的最長子串，和模式串中頭 k’+1個字符組成的子串相等，即 ″t0t1…tk’ 1tk’ ″!= ″tjk’tjk’+1…tj 1tj″ 這就是說 next[j+1]=k’+1，即 next[j+1]=next[k]+1 同理，若 tk’!=tj，則將模式繼續(xù)向右滑動直至將模式中第k″=next[k’]個字符和 tj對齊， …… ，依次類推，直至 tj和模式中某個字符匹配成功或者不存在任何 k’(0k’j)滿足等式″t0t1…tk’ 1tk’ ″!= ″tjk’tjk’+1…tj 1tj″，則 next[j+1]=0 例如，模式串 t=″abaabcac″，如圖 ，已求得前6個字符的 next[]值，現(xiàn)在要求 next[6]，因為 next[5]=2，又 t5!=t2，則需要比較 t5和 t1(因為 next[2]=0),這相當(dāng)于將子串模式向右滑動。由于 t5!=t0，而且因 next[0]=1，所以 next[6]=0；又由 next[6] =0，并且 t6=t0，則next[7]=next[6]+1=1。通過上面分析，可得求 next值算法如下。 j 0 1 2 3 4 5 6 7 模式串 a b a a b c a c next[j] 1 0 0 1 1 2 0 1 ? 算法 求 next[]數(shù)組算法。 ? get_next(char t[], int next[],int n) ? { int j,k。 ? j=0。k=1。 next[0]=1。 ? while(jn) ? if(k==1)||t[j]==t[k]) { j++。 k++。 next[j]=k。 } ? else k=next[k]。 ? } 例 子串替換是字符串結(jié)構(gòu)的常用算法。它將主串 s中所有和模式串 t相等的子串用新串 v替換。要實現(xiàn)該算法，顯然要進行多次模式匹配，以定位和 t相等的子串位置。在定位之后，進行字符替換時，應(yīng)考慮以下三種情形： (1)若 t的長度小于 v的長度，則主串 s需要擴充。 (2)若 t和 v的長度相等，為簡單替換。 (3)若 t的長度大于 v的長度，則主串 s需要縮減。 算法 利用模式匹配算法實現(xiàn)子串替換運算 /* s[]為主串， t[]模式串， v[]為新串 */ void substr(char s[],char t[],char v[]) { int s_len,t_len,v_len,s_i,t_i,v_i,gap,i,j。 s_len=length(s)。 t_len=length(t)。 v_len=length(v)。 gap=v_lent_len。 /* gap為新串和模式串的長度差 */ for(s_i=0。 s_i+t_len=s_len。) { for(t_i=0。 s_is_len amp。amp。 t_it_len。) /*利用 BF算法定位模式串 t*/ if(s[s_i]==t[t_i]) { s_i++。 t_i++。 } else { s_i=s_it_i+1。 t_i=0。 } if(t_i=t_len) /* 位模式串定位成功，以下是三種字符替換 */ { if(gap0) /* 擴充 s串 gap個單元，留意移位操作的方向 */ for(i=s_len1。 i=s_i。 i) s[i+gap]=s[i]。 if(gap0) /* 縮減 s串 gap個單元，留意移位操作的方向 */ for(i=s_i。 i=s_len1。 i++) s[i+gap]=s[i]。 for(i=s_it_len,j=0。 jv_len。 i++,j++) s[i]=v[j]。 s_len=s_len+gap。 /* 調(diào)整 s[]的長度 */ s_i=s_i+gap。 /* 為下次定位模式串，調(diào)整 s[]中的起始位置 */ } } s[s_len]=39。\039。 }
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1