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