最小循环节
题目链接
题意简述
我们需要找到一个字符 \(s\) 的最短的循环节，对循环节的定义为，当一个字符串 \(t\) 能够通过若干次自己加自己得到字符串 \(s\) ，我们就称 \(t\) 是 \(s\) 的一个循环节。
思路简述
根据题意，字符串 \(s\) 本身就是自己的一个循环节。所以，当我们找不到更小的循环节时，我们就可以输出 \(n\) 。
接下来，我们就要找到比 \(s\) 本身更短的循环节，考虑 \(KMP\) 中对 \(next\) 数组的定义，它记录了一个字符串每一个前缀的 \(border\) ，我们会惊奇的发现，这个定义与循环节的定义有异曲同工之妙。
假设 \(s\) 的最短循环节的长度，就是 \(next_|s_|\) ，这貌似是对的，但我们仍能举出反例，如：
\[ abababab \to next_|s_| \to 6 \to error \]这个样例的循环节应该是 \(ab\) ，长度应该是 \(2\)。
我们继续观察对 \(next\) 数组的定义，发现，他记录的是每一个前缀的 \(border\) 是关于真前缀与真后缀的，即不可能是这个前缀本身。所以，我们就可以考虑
标签：前缀,题解,最小,next,循环,字符串,我们,定义 From： https://www.cnblogs.com/optimist-skm/p/18325011