05 2009 档案

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

posted @ 2009-05-10 21:59 梦想飞扬 阅读(2848) | 评论 (2)  编辑 |