工學(xué)第三章串ppt課件-wenkub.com
2024-10-31 20:42 本頁(yè)面
【正文】 他有一個(gè)奇妙的承諾：在他定期進(jìn)行的講座中，會(huì)不斷提出一些新的難題。 第 3章 特殊線性表 ——串 a b a b c a b c a c b a b a b c i j i j i j 第一趟， i=3， j=3失敗， i不動(dòng) next[3]=1， j滑動(dòng)到 1的位置 第 3章 特殊線性表 ——串 a b a b c a b c a c b a b a b c a c i j i j i j i j i j 第二趟 i=7， j=5失敗， i不動(dòng) next[5]=2， j滑動(dòng)到 2的位置 第 3章 特殊線性表 ——串 a b a b c a b c a c b a b a b c a c i j i j i j i j i j 第三趟， i=11， j=6， T中全部字符都比較完畢，匹配成功 第 3章 特殊線性表 特殊線性表 棧 隊(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í)間性能 第 3章 特殊線性表 1938年出生， 25歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士，留校任教， 28歲時(shí)任副教授。 } else k=next[k]。 k=0。 // Next[j]=1表示從模式串頭部開(kāi)始進(jìn)行字符比較 （ 2） next[ j ]怎么計(jì)算？ 怎樣計(jì)算模式 T所有可能的失配點(diǎn) j 所對(duì)應(yīng)的 next[j]？ 從兩頭往中間比較 模 式 串 T： a b a a b c a c 可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位 k=next[j] : next[ j ]＝ 0 當(dāng) j＝ 1時(shí) max { k |1kj 且‘ T1…T k1?=?Tj(k1) …T j1? } 1 其他情況 0 1 2 2 3 1 2 討論： j=1時(shí) , next[ j ]≡ 0； //屬于“ j=1”情況 。 可見(jiàn)，模式中 相似部分越多，則 next[j]函數(shù)越大 ，它既表示 模式 T字符之間的相關(guān)度越高，也表示 j位置以前與主串 部分匹配 的字符數(shù)越多。 如何確定模式的滑動(dòng)距離？ 第 3章 特殊線性表 ——串 2． KMP算法 ① KMP算法設(shè)計(jì)思想 ② KMP算法的推導(dǎo)過(guò)程 ③ KMP算法的實(shí)現(xiàn) （ 關(guān)鍵技術(shù) :計(jì)算 next[j]） ④ KMP算法的時(shí)間復(fù)雜度 第 3章 特殊線性表 ——串 ① KMP算法設(shè)計(jì)思想： 盡量利用已經(jīng) 部分匹配 的結(jié)果信息，盡量讓 i不要回溯，加快模式串的滑動(dòng)速度。 不成功的匹配都發(fā)生在串 T的第一個(gè)字符。 } } if (jT[0]) return start。 j++。start=1。 } //i和 j分別回溯 } if (jT[0]) return (ij+1)。 (j=T[0])) { if (S[i]==T[j]) {i++。 si …… …… tj 模式 T 主串 S … i j 回溯 i 回溯 j BF算法的基本思想圖解 本趟匹配開(kāi)始位置 第 3章 特殊線性表 ——串 si …… 主串 S 模式 T j i tj … BF算法的基本思想圖解 第 3章 特殊線性表 ——串
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1