首页 > 代码库 > KMP (next数组的性质及证明)
KMP (next数组的性质及证明)
性质:如果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数组的性质及证明)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。