字串演算法stringalgorithms(文件)
【正文】 [i] ? failure function definition : failure[i]代表最長(zhǎng)Si的 prefix與他自己的 suffix相符是多少 而failure[i] i (注意這個(gè)限制 !) KMP Algorithms ? fail function diagram(圖例 ) ? Ex: Sq = abcwerabc ? 則 failure[q] = ? ? 以本例的話 failure[q] = 2 ? 因?yàn)?Sq的 prefix最長(zhǎng) S2與後面 Sq的 suffix相等 ? 雖然 S1也符合 但是 S2才是最長(zhǎng)的 KMP Algorithms KMP Algorithms ? How to use failure function ? 主要字串 ? 比對(duì)字串 ? 當(dāng)比對(duì)出錯(cuò)誤時(shí)，我們可以怎麼省工夫 ? ? 這兩段相同 ? 你會(huì)發(fā)現(xiàn)這段字串 ? 跟綠色字串的關(guān)係 (繼續(xù) ...) KMP Algorithms ? 目前的狀況 ? T’’ = ? Sub’ = ? 有多少已經(jīng)比對(duì)過(guò) ? ? 我們會(huì)想知道 Sub ”已經(jīng)知道 ”的 Prefix最長(zhǎng)可以跟 T’的 Suffix相同的 是到哪邊 KMP Algorithms ? 新的比對(duì)的狀況 ? 我們知道因?yàn)樯舷聝蓚€(gè)子字串完全相等 ? 那這三格是 ”最長(zhǎng) ”的 prefix of T’’等於 suffix of Sub’ ? 因此就不會(huì)有 ”更好 ”的 ”省略比對(duì) ”選擇了 KMP Algorithms ? 新的比對(duì)的狀況 ? 省略不必要的比對(duì) ? 我們就拿 Sub第四個(gè)元素重新與 T第十個(gè)元素比對(duì) ? 你會(huì)發(fā)現(xiàn)找這個(gè)最長(zhǎng)的 prefix步驟其實(shí)就是 ? 假設(shè)比對(duì)到 Sub[j]不符合的時(shí)候 ? 就可以直接省略比對(duì) failure[j]個(gè)字元 並 ”重新比對(duì)一次 ”該字元 KMP Algorithms
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1