摘要: 通过分析简单字符串模式匹配算法的缺陷，引导读者观察模式串P和目标串T已比较相等字符的关系，自然而然的引入了高效的KMP算法，并对KMP算法的难点——失效函数进行重点突破，先后比较了三种失效函数的区别和联系，提供详细的代码及算法分析。最后得出结论：这样我们就学习了三种失效函数的表示方法，虽然它们对应的KMP算法代码略有不同，但其本质是一样的，就是避免回溯目标串T的下标i，并使得模式串P的下标j回溯到正确位置。同样的，不管你用什么代码来实现求解失效函数的算法，其本质都是模式串内部的模式匹配，采用递推的方式，寻找最大的相同子串。
阅读全文