小Z在无意中发现了一个神奇的OJ，这个OJ有一个神奇的功能：每日签到，并且会通过某种玄学的算法计算出今日的运势。在多次试验之后，小Z发现自己的运势按照一定的周期循环，现在他找到了你，请通过他的记录，找出他运势的循环节。
第一行一个整数n，表示小Z记录的天数
接下来n行，表示每天的运势，用一个正整数表示，相同的整数表示相同的运势，不同的整数表示不同的运势。
一行若干个整数表示所有可能的小于等于n的循环节。
6
1 2 1 1 2 1
3 5 6
对于100%的数据，n<=365，每天的运势不会爆int
果然是签到题。
当然最暴力的解法是O(n*n*n)
这里数据范围比较小，我们考虑O(n*n)的算法
先枚举重复串的长度，判断时，用错位比较法
如果当前枚举的长度为k，匹配后缀S(1)和后缀S(k+1)的最长公共前缀是n-k的话，证明k是一个符合本题题意的循环节
要优化的话不能用后缀数组，用个kmp吧，我倒是直接暴力了
#include<stdio.h> #include<string.h> #define N 400 inline int Rin(){ int x=0,c=getchar(),f=1; for(;c<48||c>57;c=getchar()) if(!(c^45))f=-1; for(;c>47&&c<58;c=getchar()) x=(x<<1)+(x<<3)+c-48; return x*f; } int n,a[N],top,pb[N]; inline bool jud(int k){ for(int i=1;i<=n-k;i++) if(a[i]^a[k+i]) return false; return true; } int main(){ freopen("sign.in","r",stdin); freopen("sign.out","w",stdout); n=Rin(); for(int i=1;i<=n;i++) a[i]=Rin(); for(int i=1;i<n;i++) if(jud(i)) pb[++top]=i; for(int i=1;i<=top;i++) printf("%d ",pb[i]); printf("%d\n",n); fclose(stdin); fclose(stdout); return 0; }
[模拟赛FJOI Easy Round #2][T1 sign] (模拟+求字符串重复字串)
原文：http://www.cnblogs.com/keshuqi/p/6262416.html