KMP字符串匹配 1. KMP字符串匹配的原理 Knuth-Morris-Pratt算法(简称KMP),是一种非常高效的字符串匹配。设n为文本的长度,m为待查找文本模板的长度,则预处理时间需要O(m),匹配时间需要O(n)。 1.预处理阶段。KMP字符串匹配的原理就是为待查找的字符串模板创建一个前缀函数,该前缀函数得到对于模板每一个子字符串(1~i),若有相同的长度的前缀和相同的长度的后缀的字符串相同的话,返回前缀/后缀的最大长度。可能这个概念说的有点模糊,看一个例子: 例如ababc这个自字符串模板,前缀函数的值…

2015年9月28日 0条评论 10点热度 阅读全文