華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)課件第四章(陳波)(參考版)
2025-01-02 23:45本頁面
【正文】 } 求模式串 t的 next函數(shù)值算法 4. 串的應(yīng)用 ——KMP模式匹配算法 1. 在串 s和串 t中分別設(shè)比較的起始下標(biāo) i和 j； 2. 循環(huán)直到 s中所剩字符長度小于 t的長度或 T中所有字符均比較完畢 如果 s[i]=t[j]， 繼續(xù)比較 S和 T的下一個字符；否則 將 j向右滑動到 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算法進行模式匹配，當(dāng) s0s1s2s3s4=p0p1p2p3p4，且s5≠p5時，應(yīng)進行 比較。 next[j]=k。 while (jt[0]) if ((k==0)| |(t[j]= =t[k])) { j++。 j=1。next[j]=1表示從模式串頭部開始進行字符比較 j=1時 , next[ j ]＝ 0； j=2時 , next[ j ]＝ 1； j=3時 , t1≠t2，因此， k=1； j=4時 , t1＝ t3，因此， k=2； j=5時 , t1＝ t4，因此， k=2； 以此類推。 4. 串的應(yīng)用 ——KMP模式匹配算法 4. 串的應(yīng)用 ——KMP模式匹配算法 ? 計算 next[j]的方法： ? 當(dāng) j=1時， next[j]=0； //next[j]=0表示根本不進行字符比較 ? 當(dāng) j1時， next[j]的值為：模式串的位置從 1到 j1構(gòu)成的串中所出現(xiàn)的首尾相同的子串的最大長度加 1。 從第 1位往右 經(jīng)過 k1位 從 j1位往左 經(jīng)過 k1位 k＝ max { k |1kj 且 T1…T k1＝ Tj(k1) …T j1 } T1…T k1＝ Tj(k1) …T j1的物理意義是什么？ 模式應(yīng)該向右滑多遠才是最高效率的 ? 4. 串的應(yīng)用 ——KMP模式匹配算法 next[ j ]＝ 0 當(dāng) j＝ 1時 //不比較 max { k | 1kj 且 T1…T k1=Tj(k1) …T j1 } 1 其他情況 令 k = next[ j ]，則： next[j]函數(shù)表征著模式 T中最大相同首子串和尾子串（真子串）的長度。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。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。 ? 如何確定模式的滑動距離？ i=3， j=3失敗； s2=t2。 11 1 (
物理相關(guān)推薦
鄂ICP備17016276號-1