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;所以得出公式;

原文地址:https://www.cnblogs.com/wuwangchuxin0924/p/5977503.html