工學(xué)第三章串ppt課件-在線瀏覽
2024-12-21 20:42本頁(yè)面
【正文】 標(biāo) i和 j； 2. 循環(huán)直到 S中所剩字符個(gè)數(shù)小于 T的長(zhǎng)度或 T的所有字符均比較完 如果 S[i]=T[j]， 繼續(xù)比較 S和 T的下一個(gè)字符；否則 將 i和 j回溯 ， 準(zhǔn)備下一趟比較； 3. 如果 T中所有字符均比較完 ， 則匹配成功 ， 返回匹配的起始比較下標(biāo)；否則 ， 匹配失敗 ， 返回 0； BF算法用偽代碼 : 第 3章 特殊線性表 ——串 int BF(char S[ ], char T[ ]) { i=1。 //設(shè)置比較的起始下標(biāo) while ((i=S[0]) amp。 (j=T[0])) { if (S[i]==T[j]) {i++。} else {i=ij+2。 } //i和 j分別回溯 } if (jT[0]) return (ij+1)。 //的起始下標(biāo) } //S[0]、 T[0]分別存放串 S和串 T的長(zhǎng)度 BF C++算法 int BF(char S[ ], char T[ ]) { i=1。start=1。amp。 j++。 i=start。 } } if (jT[0]) return start。 } 第 3章 特殊線性表 ——串 第 3章 特殊線性表 ——串 設(shè)主串 s=“ababcabcacbab”， 模式 t=“abcac”， BF算法的匹配過(guò)程如圖 ： a b a b c a b c a c b a b a b c 結(jié)論： i=3， j=3 失敗； i回溯到 2， j回溯到 1 第1趟 i j i j i j i j 第 3章 特殊線性表 ——串 a b a b c a b c a c b a b a i j i j 第2趟 i=2， j=1失敗 i回溯到 3， j回溯到 1 第3趟 a b a b c a b c a c b a b a b c a c i=7， j=5失敗 i回溯到 4， j回溯到 1 i j i j i j i j i j j i 第 3章 特殊線性表 ——串 第4趟 a b a b c a b c a c b a b a i j i=4， j=1失敗 i回溯到 5， j回溯到 1 j i 第5趟 a b a b c a b c a c b a b i j a j i i=5， j=1失敗 i回溯到 6， j回溯到 1 第 3章 特殊線性表 ——串 第6趟 a b a b c a b c a c b a b a b c a c i=11， j=6， t 中 全 部字符都比較完畢 ， 匹配成功 。 不成功的匹配都發(fā)生在串 T的第一個(gè)字符。 第 3章 特殊線性表 ——串 能否加快模式串的滑動(dòng)速度？ 能！利用已部分匹配過(guò)的信息使主串 S的指針 i不必回溯，最壞情況也能達(dá)到 O(n+m) 為什么 BF算法時(shí)間性能低？ 在每趟匹配不成功時(shí)存在大量 回溯 ，沒(méi)有利用已經(jīng)部分匹配的結(jié)果。 如何確定模式的滑動(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)速度。 式中僅剩一個(gè)未知數(shù) k， 理論上已可解！ 根據(jù)模式串 T的規(guī)律： ‘ T1…T k1?=?Tj(k1) …T j1? 由當(dāng)前失配位置 j(已知 ) ，可以 歸納 出計(jì)算新起點(diǎn) k的表達(dá)式。 可見(jiàn)，模式中 相似部分越多，則 next[j]函數(shù)越大 ，它既表示 模式 T字符之間的相關(guān)度越高，也表示 j位置以前與主串 部分匹配 的字符數(shù)越多。 next[ j ]＝ max { k |1kj 且‘
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1