kmp 中 next 数组的周期性质
原文链接：https://www.acwing.com/solution/content/4614/
引理：
对于某一字符串 S[1～i]，在它众多的next[i]的“候选项”中，如果存在某一个next[i]，使得: i% (i−next[i])==0，那么 S[1～ (i−next[i])]可以为 S[1～ i]的循环元而 i/(i−next[i])即是它的循环次数 K。
证明如下：
如图，next[i]=j,由定义得红色部分两个子串完全相同。 即S[1～j]=Sm～i
如果我们在两个子串的前面框选一个长度为 m 的小子串(橙色部分)。
可以得到：S[1～m]=S[m~b]
如果在紧挨着之前框选的子串后面再框选一个长度为 m 的小子串(绿色部分)，同样的道理，
可以得到：S[m～b]=S[b～c]
又因为：S[1～m]=S[m～b]
所以：S[1～m]=S[m～b]=S[b～c]
如果一直这样框选下去，无限推进，总会有一个尽头。 当满足 i% m==0时，刚好可以分出 K个这样的小子串， 且形成循环(K=i/m)
因此我们需要从 1～N扫一遍，判断如果 next[i]可以整除 i，即满足 i% (i−next[])==0，那么就可以肯定S[1～ (i−next[i])]是 S[1～i]的最小循环元，而i/(i−next[i])即是它的最大循环次数 K，直接依次输出这些 i 和 K即可。
那么为什么只判断 next[i]而不判断 next[?]呢？ （注：next[i]和next[?]表述的意义不同，为方便描述，这里定义next[?]为next[i]的“候选项”中的某一个）
实际上由这道题可以总结出很多结论：
结论
结论一：
若i−next[i]可整除i,则s[1～i]具有长度为i−next[i]的循环元，即s[1～i−next[i]]。
(前面的一大堆文字和图片已经给出了这个结论的证明，同时结论一也是后面推导其他结论的理论基础）
结论二： 若i−next[?]可整除i,则s[1～i]具有长度为i−next[?]的循环元，即s[1～i−next[?]] (用与结论一同样的证明方法可以推导出结论二) (由此处可知，i−next[?]想用作循环元要满足的条件是：i−next[?]可整除i)。
结论三： 任意一个循环元的长度必定是最小循环元长度的倍数
结论四： 如果i−next[i]不可整除i，s[1～i−next[?]]一定不能作为s[1～i]的循环元。
关于结论四的证明和扩展：
①.如果s[1～i−next[i]]不能作为s[1～i]循环元，那么s[1～i−next[?]]也都一定不能作为s[1～i]的循环元。 (即结论四)
②.如果i−next[i]不可整除i，s[1～i]一定不存在循环元。
③.如果i−next[i]不可整除i，i−next[?]也都一定不可整除i。
④.如果s[1～m]是s[1～i]的循环元，next[i]一定为i−m(i−m一定为next[i])。(在算法竞赛进阶指南上有这么一句话：如果s[1～m]为s[1～i]的循环元，i−m一定是next[i]的“候选项”，与此处意义略有不同)
⑤.若m=i−next[i]，j=next[?]，next[j]=j−m。(无论可否整除i) (由④扩展而来)
一些题外话：
关于③的证明，有一个很有趣的想法。 有两个数a，c和一个数的集合b，且b与a有一定的关系(限制)。 已知a不可整除c，证明x(x∈b)不可整除c(目前尚未成功)。 虽然表面上看起来并没有什么用，但这种思想把图形匹配转 化为了代数证明。 如果有大佬感兴趣可以思考一下。。。
附：来自某李姓Math大佬。 ②③④比较好理解，这个⑤是个什么意思呢？
其实不难懂，通俗点说就是i−next[?]一定是在m的倍数处(m,2m,3m…)，如果有循环，也可以说是i−next[?]一定在循环节点上,或者说是一定在我们先前图片中框选的黑色块的边界相 邻处，不可能在某个黑色块的中间（如图红色为不可能的情况）
注意一下这个等式：i−next[j]=i−j+m 可以化简为：next[j]=j−m 那么可以发现每个next[?]和next[next[?]]之间刚好相差m， 只是要由⑤推导①的话，用化简前的样子似乎会更好懂一些。
假如④⑤得证，那么它们和①有什么关系呢？
如果i−next[?]一定是在m的倍数处(m=i−next[i]) 因为当m不可整除i时，m的倍数也不可整除i，
所以i−next[?]均不满足作为s[1～i]循环元的条件(前面已提到过“条件”具体指什么)。
因此，⑤→①得证。
如何证明④或者⑤？
如图，j=next[i]，m=i−next[i]
先按照与之前相同的方法先将s[1～i]划分成K个黑色块
j0=next[j]，n=i−next[j]，假设n不在m的倍数处，如图红色。
同样的，框选出红色块。
然后再作一些辅助线。接下来就开始推理。
设v=j−j0 先看左边：s[1～1+v]=s[m～m+v]，s[1+v～1+2v]=s[m+v~m+2v]
再看右边： s[1～1+v]=s[m+v～m+2v]
综合可得：s[1～1+v]=s[m～m+v]=s[m+v～m+2v]=s[1+v～1+2v]
无限的推进，再推进，辅助线划分出的长度为v的区域全部相等，直至边界。而此时的边界出现了两种情况：
⑴v可整除i。
此时刚好将s[1～i]分成了若干个完全相同的长度为v的小块，明显形成了循环元s[1～v]，那么next[i]至少应为i−v，这与之前的next[i]=j相矛盾。
⑵v不可整除i。
观察下列图片，你发现了什么？
将蓝圈处放大，发现了一种交叉相等的情况(如图绿色处)。
再把它压扁，并取几个新的名字1′,m′,j′,i′。
此时它变得和初始的情况一模一样，于是经过相同的操作后，再一次使出了无限 推进，假如每次的v′都不可整除m′，那么就一路推了边界：v′=1 1可以整除任何数，于是s[1～i]形成了长度为1的循环元，矛盾。
当n不在m的倍数处时，一定会出现矛盾，所以假设不成立。
因此④得证。同理⑤也得证。
⬅️ 剪布花条 🏠 00-刷题理模型 ➡️ 拓展 循环结问题(头疼警告）
💬 评论