【题目来源】：https://vjudge.net/problem/POJ-2406 【题意】 给出一个字符串，问其最小循环周期是多少。 【思路】 利用kmp中next数组的特殊性，也就是若字符串长度为len，则在1~len里，假设i在1~n，那么假设长度为i，那么其的最小循环周期是i-next[i]。 可以自行证明。 【代码】
#include<set> #include<map> #include<stack> #include<cmath> #include<queue> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<limits.h> #include<algorithm> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int mod=1e9+7; const double esp=1e-5; typedef unsigned long long ll; typedef long long LL; char s[1000000+10]; int nexts[1000000+10]; int len; void get_next() { int i,j; j=nexts[0]=-1; i=0; while(i<len) { while(-1!=j&&s[i]!=s[j]) j=nexts[j]; nexts[++i]=++j; } } int main() { while(~scanf("%s",s)&&s[0]!='.') { len=strlen(s); get_next(); int ans=1; if(len%(len-nexts[len])==0) ans=len/(len-nexts[len]); printf("%d\n",ans); } }