poj2406Power Strings（KMP）

KMP的nex数组求循环节。
 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=10000010;
 4 char s[maxn];
 5 int nex[maxn];
 6 int n;
 7 void getnex()
 8 {
 9     n=strlen(s);
10     int i=0,j=-1;
11     nex[0]=-1;
12     while(i<n)
13     {
14         if(j==-1||s[i]==s[j])
15             nex[++i]=++j;
16         else j=nex[j];
17     }
18 }
19 
20 int main()
21 {
22     while(scanf("%s",s)&&s[0]!='.')
23     {
24         getnex();
25         if(n%(n-nex[n])==0&&n!=n-nex[n]) printf("%d
",n/(n-nex[n]));
26         else printf("1
");
27     }
28 }