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