KMP算法实现代码
2018-07-20 来源：open-open
在文章里只给出了算法代码以及解释，后边的留下了一份中文一份英文的参考博文地址以便深刻理解KMP算法。ps：中文的亲测，解释原理简单易懂。
KMP算法
算法思想
相比蛮力算法，KMP算法预先计算出了一个哈希表，用来指导在匹配过程中匹配失败后尝试下次匹配的起始位置，以此避免重复的读入和匹配过程。这个哈希表被叫做“部分匹配值表(**Particial match table**)”，它的设计是算法精妙之处。部分匹配值表
要理解部分匹配值表，就得先了解字符串的前缀(prefix)和后缀(postfix)。
前缀:除字符串最后一个字符以外的所有头部串的组合。
后缀：除字符串第一个字符以外的所有尾部串的组合。
部分匹配值：一个字符串的前缀和后缀中最长共有元素的长度。
举例说明：字符串ABCAB
前缀：{A， AB， ABC， ABCA}
后缀：{BCAB， CAB， AB， B}
部分匹配值：2 （AB）
而所谓的部分匹配值表，则为模式串的所有前缀以及其本身的部分匹配值。
前缀:除字符串最后一个字符以外的所有头部串的组合。
后缀：除字符串第一个字符以外的所有尾部串的组合。
部分匹配值：一个字符串的前缀和后缀中最长共有元素的长度。
举例说明：字符串ABCAB
前缀：{A， AB， ABC， ABCA}
后缀：{BCAB， CAB， AB， B}
部分匹配值：2 （AB）
而所谓的部分匹配值表，则为模式串的所有前缀以及其本身的部分匹配值。
标签： 代码
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。
上一篇:c#xml文档操作类(2)
下一篇:DOM4J生成、解析XML实例
最新资讯
热门推荐