现在的位置: 首页 > 综合 > 正文

关于Kmp算法的一点小节

2013年12月13日 ⁄ 综合 ⁄ 共 1034字 ⁄ 字号 评论关闭

      虽然勉强的将代码帖出来了,但是其中的理论实际上自己还并没有完全搞懂。不过这里说说我的理解吧,全当跟大家交流。不对之处还请海涵。

      KMP算法首先要做的就是得到这个next模式匹配数组。这个数组记录的值。是其后缀项,与起始前缀项所匹配的字符个数。第一个值next[0] = 0;然后后面的一一对比,与前缀项相同就加1保存,不同,就将前缀项回退,这里采用的就是j = next[j];这里面存放的是前缀项中匹配的字符个数。由此便能将前缀项与后缀项匹配对应。

      网上的这个图很好的反映了这种情况:如下图

 

p(j = 1) = 0;

p(j = 2) = 0;

p(j = 3) = 1;

p(j = 4) = 1;

p(j = 5) = 2;

p(j = 6) = 0;

p(j = 7) = 1;

p(j = 8) = 0;

注意这里next是在模式匹配时,需要在源串中右移的位数。

 

抱歉!评论已关闭.