首页 > 编程语言 > 详细

KMP (next数组的性质及证明)

时间:2016-10-19 16:36:32      阅读:128      评论:0      收藏:0      [点我收藏+]

性质:如果len%(len-next[len-1])==0,则字符串中必存在最小循环节,且循环次数即为len/(len-next[len-1]);

证明:在前len个字符组成的字符串,存在最小循环节k,那么next[len-1]=len-k;为什么呐?因为next数组的定义就是最大前后缀相同的子串的长度,len的总长度减去最小循环节,比如有3个循环节,减去一个剩下两个,就是最大循环节)那么循环次数就是len/(len-next[len-1]);因为len-next[len-1]=k;所以得出公式;

 

KMP (next数组的性质及证明)

原文:http://www.cnblogs.com/wuwangchuxin0924/p/5977503.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!