華北水利學(xué)院數(shù)據(jù)結(jié)構(gòu)第四章(陳波)-資料下載頁
2025-05-12 10:18本頁面
【正文】 滑多遠才是最高效率的 ? 4. 串的應(yīng)用 ——KMP模式匹配算法 next[ j ]＝ 0 當 j＝ 1時 //不比較 max { k | 1kj 且 T1…T k1=Tj(k1) …T j1 } 1 其他情況 令 k = next[ j ]，則： next[j]函數(shù)表征著模式 T中最大相同首子串和尾子串（真子串）的長度。 可見，模式中相似部分越多，則 next[j]函數(shù)越大，它既表示模式 T 字符之間的相關(guān)度越高，模式串向右滑動得越遠，與主串進行比較的次數(shù)越少，時間復(fù)雜度就越低。 4. 串的應(yīng)用 ——KMP模式匹配算法 4. 串的應(yīng)用 ——KMP模式匹配算法 ? 計算 next[j]的方法： ? 當 j=1時， next[j]=0； //next[j]=0表示根本不進行字符比較 ? 當 j1時， next[j]的值為：模式串的位置從 1到 j1構(gòu)成的串中所出現(xiàn)的首尾相同的子串的最大長度加 1。 ? 當無首尾相同的子串時 next[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模式匹配算法 j 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next[j] 0 1 1 2 2 3 1 2 void GetNext(char t[ ]) { next[1]=0。 j=1。 k=0。 while (jt[0]) if ((k==0)| |(t[j]= =t[k])) { j++。 k++。 next[j]=k。 } else k=next[k]。 } 求模式串 t的 next函數(shù)值算法 4. 串的應(yīng)用 ——KMP模式匹配算法 1. 在串 s和串 t中分別設(shè)比較的起始下標 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， 準備下一趟比較； 3. 如果 t中所有字符均比較完畢，則返回匹配的起始下標；否則返回 0； 4. 串的應(yīng)用 ——KMP模式匹配算法 例：設(shè)主串 s=abcabcabd，模式串 p=abcabd，按 KMP算法進行模式匹配，當 s0s1s2s3s4=p0p1p2p3p4，且s5≠p5時，應(yīng)進行 比較。 A、 s5和 p2 B、 s5和 p3 C、 s1和 p0 D、 s8和 p5 4. 串的應(yīng)用 ——KMP模式匹配算法 特殊線性表 棧 隊 列 串 ⑴ 棧的定義 ⑵ 操作特性 ⑶ ADT定義 ⑴ 隊列定義 ⑵ 操作特性 ⑶ ADT定義 ⑴ 串的定義 ⑵ 基本概念 ⑶ ADT定義 順序棧 鏈 棧 循環(huán)隊列 鏈隊列 順序存儲 鏈接存儲 邏輯結(jié)構(gòu) 存儲結(jié)構(gòu) 邏輯結(jié)構(gòu) 邏輯結(jié)構(gòu) 存儲結(jié)構(gòu) 存儲結(jié)構(gòu) 比 較 模式匹配 比較 比較 ⑴ 基本操作的實現(xiàn) ⑵ 時間性能 ⑴ 基本操作的實現(xiàn) ⑵ 時間性能 特殊線性表 —— 串
法律信息相關(guān)推薦
鄂ICP備17016276號-1