题目链接：https://loj.ac/problem/10045 分析： 求一个最小的循环节，这个循环节能构成的字符串T，使给定的字符串能从T中找到。 对于kmp的next数组，len-next[len]一定是字符串的循环节。 证明如下： 文本串为T next[n]为上图蓝色的部分（即整个T前后缀相等的最大长度）
将next[n]和T从开头对齐，黄色部分为n-next[n] 接着： 黄色部分(n-next[n])和next[n]的开头一样，按照箭头的方向，依次能把T用黄色部分填满。 所以说：n-next[n]为T的循环节(n为T的长度)
为什么说n-next[n]为T的最小循环节？ 蓝色部分为next[n]，前后缀相同的部分如上图蓝色方框，对于T的最小循环节是黄色线段所标记的范围（n-next[n]）。 代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e6+10; int n,net[N]; char a[N]; void kmp(int len) { net[0]=-1; int i=0,k=-1; while(i<len) { if(k<0||a[i]==a[k]) net[++i]=++k; else k=net[k]; } } int main() { while(~scanf("%d",&n)) { scanf("%s",a); int len=strlen(a); kmp(len); printf("%d\n",len-net[len]); } return 0; }日子如流水般从指尖划过
