摘要: 通過分析簡單字符串模式匹配算法的缺陷，引導(dǎo)讀者觀察模式串P和目標(biāo)串T已比較相等字符的關(guān)系，自然而然的引入了高效的KMP算法，并對(duì)KMP算法的難點(diǎn)——失效函數(shù)進(jìn)行重點(diǎn)突破，先后比較了三種失效函數(shù)的區(qū)別和聯(lián)系，提供詳細(xì)的代碼及算法分析。最后得出結(jié)論：這樣我們就學(xué)習(xí)了三種失效函數(shù)的表示方法，雖然它們對(duì)應(yīng)的KMP算法代碼略有不同，但其本質(zhì)是一樣的，就是避免回溯目標(biāo)串T的下標(biāo)i，并使得模式串P的下標(biāo)j回溯到正確位置。同樣的，不管你用什么代碼來實(shí)現(xiàn)求解失效函數(shù)的算法，其本質(zhì)都是模式串內(nèi)部的模式匹配，采用遞推的方式，尋找最大的相同子串。
閱讀全文