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