華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)課件第四章(陳波)(完整版)
【正文】 ? 主串 ：包含子串的串。 2. 串的存儲(chǔ)結(jié)構(gòu) ——順序串 如何表示串的長(zhǎng)度 ？ 鏈接串： 用鏈接存儲(chǔ)結(jié)構(gòu) 來(lái)存儲(chǔ)串 。這個(gè)函數(shù)的調(diào)用模型如下所示： void RemoveChars(char str[],char remove[])。 第 6 趟 i j i j i j i j i j 例：主串 S=ababcabcacbab， 模式 T=abcac 4. 串的應(yīng)用 ——BF模式匹配算法 1. 在串 S和串 T中設(shè)比較的起始下標(biāo) i和 j； 2. 循環(huán)直到 S或 T的所有字符均比較完； 如果 S[i]=T[j]， 繼續(xù)比較 S和 T的下一個(gè)字符； 否則 ， 將 i和 j回溯 ， 準(zhǔn)備下一趟比較； 3. 如果 T中所有字符均比較完 ， 則匹配成功 ， 返回匹配的起始比較下標(biāo)；否則 ， 匹配失敗 ， 返回 0； 4. 串的應(yīng)用 ——BF模式匹配算法 int BFmatching(char s[ ], char t[ ]) { i=1。 } 4. 串的應(yīng)用 ——BF模式匹配算法 4. 串的應(yīng)用 ——BF模式匹配算法 ? 設(shè)串 s長(zhǎng)度為 n，串 t長(zhǎng)度為 m，在匹配成功的情況下，考慮兩種極端情況： ? 最好情況 ：不成功的匹配都發(fā)生在串 t的第一個(gè)字符。t1≠t2 ∴ t1≠s2 a b a b c a b c a c b a b i j 第 1 趟 a b c a c a b a b c a b c a c b a b a b c a c 第 3 趟 4. 串的應(yīng)用 ——KMP模式匹配算法 a b a b c a b c a c b a b a b c a c 第 3 趟 i j i=7， j=5失敗s4=t2。next[j]=1表示從模式串頭部開(kāi)始進(jìn)行字符比較 j=1時(shí) , next[ j ]＝ 0； j=2時(shí) , next[ j ]＝ 1； j=3時(shí) , t1≠t2，因此， k=1； j=4時(shí) , t1＝ t3，因此， k=2； j=5時(shí) , t1＝ t4，因此， k=2； 以此類(lèi)推。 } 求模式串 t的 next函數(shù)值算法 4. 串的應(yīng)用 ——KMP模式匹配算法 1. 在串 s和串 t中分別設(shè)比較的起始下標(biāo) i和 j； 2. 循環(huán)直到 s中所剩字符長(zhǎng)度小于 t的長(zhǎng)度或 T中所有字符均比較完畢 如果 s[i]=t[j]， 繼續(xù)比較 S和 T的下一個(gè)字符；否則 將 j向右滑動(dòng)到 next[j]位置 ， 即 j=next[j]； 如果 j=0， 則將 i和 j分別加 1， 準(zhǔn)備下一趟比較； 3. 如果 t中所有字符均比較完畢，則返回匹配的起始下標(biāo)；否則返回 0； 4. 串的應(yīng)用 ——KMP模式匹配算法 例：設(shè)主串 s=abcabcabd，模式串 p=abcabd，按 KMP算法進(jìn)行模式匹配，當(dāng) s0s1s2s3s4=p0p1p2p3p4，且s5≠p5時(shí)，應(yīng)進(jìn)行 比較。 j=1。t1≠t3 ∴ t1≠s5 a b a b c a b c a c b a b a b c a c 第 5 趟 4. 串的應(yīng)用 ——KMP模式匹配算法 a b a b c a b c a c b a b a b c a c 第 3 趟 i j i=7， j=5失敗s5=t3。 11 1 ( )( 1 ) ( 1 )12
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1