Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

Input

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Output

For each s you should print the largest n such that s = a^n for some string a.

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

Hint

This problem has huge input, use scanf instead of cin to avoid time limit exceed.

题意:

输入一个字符串，让你找出来这个串的最小循环节

题解：

对于答案就用for循环从1到n枚举（为什么不能用二分？因为这个判断没有单调性。即i不是循环节的话，你不能说i-1或者i+1也肯定不是循环节）

下一步就是判断枚举的这个i是不是循环节，怎么判断？

满足这三个条件：n%i==0 && Rank[0]-Rank[i]==1 && height[Rank[0]]==n-i

1、n%i==0这就肯定不需要说了

2、你要注意Rank[0]表示的是啥，他代表后缀[0…n]的排名是多少，如果循环节是i，那么Rank[0]-Rank[i]==Rank[i]-Rank[2*i]……==1

3、如果循环节是i，那么height[Rank[0]]==n-i,   height[Rank[0]]代表后缀[0..n]与后缀[i…n]的最长公共前缀，既然循环节是i，那么height[Rank[0]]的值也就等于n-i

还要注意这道题用后缀数组来做的话要用dc3模板，如果用Da模板会TLE

dc3模板AC代码：

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 const int maxn = 3000010;
7 #define F(x) ((x) / 3 + ((x) % 3 == 1 ? 0 : tb))
8 #define G(x) ((x) < tb ? (x) * 3 + 1 : ((x) - tb) * 3 + 2) 9 int wa[maxn], wb[maxn], Ws[maxn], wv[maxn], sa[maxn]; 10 int Rank[maxn], height[maxn],r[maxn]; 11 char s[maxn]; 12 int c0(int *r, int a, int b) 13 { 14 return r[a] == r[b] && r[a + 1] == r[b + 1] && r[a + 2] == r[b + 2]; 15 } 16 int c12(int k, int *r, int a, int b) 17 { 18 if (k == 2) 19 return r[a] < r[b] || r[a] == r[b] && c12(1, r, a + 1, b + 1); 20 return r[a] < r[b] || r[a] == r[b] && wv[a + 1] < wv[b + 1]; 21 } 22 void Rsort(int *r, int *a, int *b, int n, int m) 23 { 24 for (int i = 0; i < n; i++) wv[i] = r[a[i]]; 25 for (int i = 0; i < m; i++) Ws[i] = 0; 26 for (int i = 0; i < n; i++) Ws[wv[i]]++; 27 for (int i = 1; i < m; i++) Ws[i] += Ws[i - 1]; 28 for (int i = n - 1; i >= 0; i--) b[--Ws[wv[i]]] = a[i];
29 }
30 void dc3(int *r,int *sa,int n, int m)
31 {
32 int i, j, *rn = r + n, *san = sa + n, ta = 0, tb = (n + 1) / 3, tbc = 0, p;
33 r[n] = r[n + 1] = 0;
34 for (i = 0; i < n; i++) if (i % 3 != 0) wa[tbc++] = i;
35 Rsort(r + 2, wa, wb, tbc, m);
36 Rsort(r + 1, wb, wa, tbc, m);
37 Rsort(r, wa, wb, tbc, m);
38 for (p = 1, rn[F(wb[0])] = 0, i = 1; i < tbc; i++)
39 rn[F(wb[i])] = c0(r, wb[i - 1], wb[i]) ? p - 1 : p++;
40 if (p < tbc) dc3(rn, san, tbc, p);
41 else for (i = 0; i < tbc; i++) san[rn[i]] = i;
42 for (i = 0; i < tbc; i++) if (san[i] < tb) wb[ta++] = san[i] * 3;
43 if (n % 3 == 1) wb[ta++] = n - 1;
44 Rsort(r, wb, wa, ta, m);
45 for (i = 0; i < tbc; i++) wv[wb[i] = G(san[i])] = i;
46 for (i = 0, j = 0, p = 0; i < ta && j < tbc; p++)
47 sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
48 for (; i < ta; p++) sa[p] = wa[i++];
49 for (; j < tbc; p++) sa[p] = wb[j++];
50 }
51 void get_height(int n)
52 {
53 int i, j, k = 0;
54 for (i = 1; i <= n; i++) Rank[sa[i]] = i;
55 for (i = 0; i < n; height[Rank[i++]] = k)
56 for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; k++);
57 }
58 int main()
59 {
60 while(~scanf("%s",s))
61 {
62 int n=strlen(s);
63 if(n==1 && s[0]=='.') break;
64 for(int i=0;i<n;++i)
65 r[i]=s[i];
66 r[n]='0';
67 dc3(r,sa,n+1,200);
68 get_height(n);
69 int flag=0;
70 for(int i=1;i<n;++i) //枚举循环节长度
71 {
72 if(n%i==0 && Rank[0]-Rank[i]==1 && height[Rank[0]]==n-i)
73 {
74 flag=1;
75 printf("%d\n",n/i);
76 break;
77 }
78 }
79 if(!flag)
80 printf("1\n");
81 }
82 return 0;
83 }

Da模板TLE代码：

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6
7 const int N = 1000010;
8 int x[N], y[N], c[N];
9 int rank[N], height[N];
10 int sa[N],n,k;
11 char s[N];
12 bool pan(int *x,int i,int j,int k,int n)
13 {
14 int ti=i+k=0; i--)sa[--c[s[i]]]=i;
25 r=1;
26 x[sa[0]]=0;
27 for(int i=1; i=k)y[yn++]=sa[i]-k;
35 for(int i=0; i=0; i--)sa[--c[x[y[i]]]]=y[i];
39 swap(x,y);
40 r=1;
41 x[sa[0]]=0;
42 for(int i=1; i=len)
66 cnt++,i++;
67 if(cnt+1>=k)return 1;
68 if(i>=n)return 0;
69 while(i <=n &&height[i]<len)
70 i++;
71 cnt=0;
72 }
73 }
74
75 int main()
76 {
77 while(~scanf("%s",s))
78 {
79 n=strlen(s);
80 if(n==1 && s[0]=='.') break;
81 s[n]='0';
82 build_SA(n+1,200);
83 get_height(n);
84 //printf("%d %d %d\n",rank[0],rank[3],height[rank[0]]);
85 int flag=0;
86 for(int i=1;i<n;++i) //枚举循环节长度
87 {
88 if(n%i==0 && rank[0]-rank[i]==1 && height[rank[0]]==n-i)
89 {
90 flag=1;
91 printf("%d\n",n/i);
92 break;
93 }
94 }
95 if(!flag)
96 printf("1\n");
97 }
98 return 0;
99 }