wenbao与后缀数组

 1 #define maxn 1000001
 2 int wa[maxn],wb[maxn],wv[maxn],wss[maxn];
 3 
 4 int cmp(int *r, int a, int b, int l) {
 5     return r[a] == r[b] && r[a+l] == r[b+l];
 6 }
 7 
 8 void da(int *r, int *sa, int n, int m) {
 9     int i, j, p, *x = wa, *y = wb, *t;
10     for(i = 0; i < m; i++) wss[i] = 0;
11     for(i = 0; i < n; i++) wss[x[i]=r[i]]++;
12     for(i = 1; i < m; i++) wss[i] += wss[i-1];
13     for(i = n-1; i >= 0; i--) sa[--wss[x[i]]] = i;
14     for(j = 1, p = 1; p < n; j *= 2, m = p) {
15         for(p = 0, i = n-j; i < n; i++) y[p++] = i;
16         for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] - j;
17         for(i = 0; i < n; i++) wv[i] = x[y[i]];
18         for(i = 0; i < m; i++) wss[i] = 0;
19         for(i = 0; i < n; i++) wss[wv[i]] ++;
20         for(i = 1; i < m; i++) wss[i] += wss[i-1];
21         for(i = n-1; i>=0; i--) sa[--wss[wv[i]]] = y[i];
22         for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
23             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
24     }
25     return;
26 }
27 
28 int rank[maxn], height[maxn];
29 void calheight(int *r, int *sa, int n) {
30     int i, j, k = 0;
31     for(i = 1; i <= n; i++) rank[sa[i]] = i;
32     for(i = 0; i < n; height[rank[i++]] = k)
33         for(k ? k-- : 0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k++);
34     return;
35 }
36 
37 int RMQ[maxn];
38 int mm[maxn];
39 int best[20][maxn];
40 void initRMQ(int n) {
41     int i, j, a, b;
42     for(mm[0] =- 1, i = 1; i <= n; i++)
43         mm[i] = ((i&(i-1)) == 0) ? mm[i-1]+1 : mm[i-1];
44     for(i = 1; i <= n; i++) best[0][i] = i;
45     for(i = 1; i <= mm[n]; i++)
46         for(j = 1; j <= n+1-(1<<i); j++) {
47             a = best[i-1][j];
48             b = best[i-1][j+(1<<(i-1))];
49             if(RMQ[a] < RMQ[b]) best[i][j] = a;
50             else best[i][j] = b;
51         }
52     return;
53 }
54 
55 int askRMQ(int a, int b) {
56     int t;
57     t = mm[b-a+1];
58     b -= (1<<t)-1;
59     a = best[t][a];
60     b = best[t][b];
61     return RMQ[a] < RMQ[b] ? a : b;
62 }
63 int lcp(int a, int b) {
64     int t;
65     a = rank[a];
66     b = rank[b];
67     if(a > b)  t = a, a = b, b = t;
68     return(height[askRMQ(a+1, b)]);
69 }
70 
71 int sa[maxn], r[maxn];

 1 #define maxn 1000009
 2 #define F(x) ((x)/3+((x)%3 == 1?0:tb))
 3 #define G(x) ((x)<tb ? (x)*3+1 : ((x)-tb)*3+2)
 4 
 5 int wa[maxn], wb[maxn], wv[maxn], wss[maxn];
 6 int c0(int *r, int a, int b) {
 7     return r[a] == r[b] && r[a+1] == r[b+1] && r[a+2] == r[b+2];
 8 }
 9 int c12(int k, int *r, int a, int b) {
10     if(k == 2) return r[a] < r[b] || r[a] == r[b] && c12(1, r, a+1, b+1);
11     else return r[a] < r[b] || r[a] == r[b] && wv[a+1] < wv[b+1];
12 }
13 
14 void sort(int *r, int *a, int *b, int n, int m) {
15     int i;
16     for(i = 0; i < n; i++) wv[i] = r[a[i]];
17     for(i = 0; i < m; i++) wss[i] = 0;
18     for(i = 0; i < n; i++) wss[wv[i]] ++;
19     for(i = 1; i < m; i++) wss[i] += wss[i-1];
20     for(i = n-1; i >= 0; i--) b[--wss[wv[i]]] = a[i];
21     return;
22 }
23 
24 void dc3(int *r, int *sa, int n, int m) {
25     int i, j, *rn = r+n, *san = sa+n, ta = 0, tb = (n+1)/3, tbc=0, p;
26     r[n] = r[n+1] = 0;
27     for(i = 0; i < n; i++) if(i%3 != 0) wa[tbc++] = i;
28     sort(r+2, wa, wb, tbc, m);
29     sort(r+1, wb, wa, tbc, m);
30     sort(r, wa, wb, tbc, m);
31     for(p = 1, rn[F(wb[0])] = 0, i = 1; i < tbc; i++)
32         rn[F(wb[i])] = c0(r, wb[i-1], wb[i]) ? p-1 : p++;
33     if(p < tbc) dc3(rn, san, tbc, p);
34     else for(i = 0; i < tbc; i++) san[rn[i]] = i;
35     for(i = 0; i < tbc; i++) if(san[i] < tb) wb[ta++] = san[i]*3;
36     if(n%3 == 1) wb[ta++] = n-1;
37     sort(r, wb, wa, ta, m);
38     for(i = 0; i < tbc; i++) wv[wb[i]=G(san[i])] = i;
39     for(i = 0, j = 0, p = 0; i < ta && j < tbc; p++)
40         sa[p] = c12(wb[j]%3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
41     for(; i < ta; p++) sa[p] = wa[i++];
42     for(; j < tbc; p++) sa[p] = wb[j++];
43     return;
44 }
45 
46 int rank[maxn*3], height[maxn*3];
47 void calheight(int *r, int *sa, int n) {
48     int i, j, k = 0;
49     for(i = 1; i <= n; i++) rank[sa[i]] = i;
50     for(i = 0; i < n; height[rank[i++]] = k)
51         for(k ? k-- : 0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k++);
52     return;
53 }
54 
55 int RMQ[maxn];
56 int mm[maxn];
57 int best[20][maxn];
58 void initRMQ(int n) {
59     int i, j, a, b;
60     for(mm[0] =- 1, i = 1; i <= n; i++)
61         mm[i] = ((i & (i-1)) == 0) ? mm[i-1]+1 : mm[i-1];
62     for(i = 1; i <= n; i++) best[0][i] = i;
63     for(i = 1; i <= mm[n]; i++)
64         for(j = 1; j <= n+1-(1<<i); j++) {
65             a = best[i-1][j];
66             b = best[i-1][j+(1<<(i-1))];
67             if(RMQ[a] < RMQ[b]) best[i][j] = a;
68             else best[i][j] = b;
69         }
70     return;
71 }
72 
73 int askRMQ(int a, int b) {
74     int t;
75     t = mm[b-a+1];
76     b -= (1<<t)-1;
77     a = best[t][a];
78     b = best[t][b];
79     return RMQ[a] < RMQ[b] ? a : b;
80 }
81 
82 int lcp(int a, int b) {
83     int t;
84     a = rank[a];
85     b = rank[b];
86     if(a > b) t = a, a = b, b = t;
87     return(height[askRMQ(a+1, b)]);
88 }
89 
90 int sa[maxn*3], r[maxn];

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 
 5 const int maxn = 1009;
 6 int a[maxn], sa[maxn], len;
 7 char str[maxn];
 8 
 9 int wa[maxn], wb[maxn], wv[maxn], wws[maxn];
10 int cmp(int *r, int a, int b, int l){
11     return r[a] == r[b] && r[a+l] == r[b+l];
12 }
13 //sa from 0 -> n-1
14 void da(int *r, int *sa, int n, int m){
15     int i, j, p, *x = wa, *y = wb, *t;
16     for(i = 0; i < m; i++) wws[i] = 0;
17     for(i = 0; i < n; i++) wws[x[i] = r[i]]++;
18     for(i = 1; i < m; i++) wws[i] += wws[i-1];
19     for(i = n-1; i >= 0; i--) sa[--wws[x[i]]] = i;
20     for(j = 1,p = 1; p < n; j *= 2, m = p){
21         for(p = 0,i = n-j; i<n;i++) y[p++] = i;
22         for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i]-j;
23         for(i = 0; i < n; i++) wv[i] = x[y[i]];
24         for(i = 0; i < m; i++) wws[i] = 0;
25         for(i = 0; i < n; i++) wws[wv[i]] ++;
26         for(i = 1; i < m; i++) wws[i] += wws[i-1];
27         for(i = n-1; i >= 0; i--) sa[--wws[wv[i]]] = y[i];
28         for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
29             x[sa[i]] = cmp(y,sa[i-1], sa[i],j) ? p-1 : p++;
30     }
31     return ;
32 }
33 
34 int Rank[maxn], height[maxn];
35 void calheight(int *r, int *sa, int n){
36     int i, j, k = 0;
37     for(i = 1; i <= n; i++) Rank[sa[i]] = i;
38     for(i = 0; i < n; height[Rank[i++]] = k)
39         for(k ? k-- : 0, j = sa[Rank[i]-1]; r[i+k] == r[j+k]; k++);
40     return;
41 }
42 
43 
44 int main(){
45     int t;
46     scanf("%d", &t);
47     while(t--){
48         scanf("%s", str);
49         int len = strlen(str);
50         for(int i = 0; i < len; ++i) a[i] = str[i];
51         a[len] = 1;
52         da(a, sa, len+1, 555);
53         calheight(a, sa, len);
54         int sum = 0;
55         for(int i = 1; i <= len; ++i){
56             sum = sum + len-sa[i]-height[i];
57         }
58         printf("%d\n", sum);
59     }
60     return 0;
61 }

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 
 6 const int maxn = 20009;
 7 int a[maxn], sa[maxn], len;
 8 char str[maxn];
 9 
10 int wa[maxn], wb[maxn], wv[maxn], wws[maxn];
11 int cmp(int *r, int a, int b, int l){
12     return r[a] == r[b] && r[a+l] == r[b+l];
13 }
14 //sa from 0 -> n-1
15 void da(int *r, int *sa, int n, int m){
16     int i, j, p, *x = wa, *y = wb, *t;
17     for(i = 0; i < m; i++) wws[i] = 0;
18     for(i = 0; i < n; i++) wws[x[i] = r[i]]++;
19     for(i = 1; i < m; i++) wws[i] += wws[i-1];
20     for(i = n-1; i >= 0; i--) sa[--wws[x[i]]] = i;
21     for(j = 1,p = 1; p < n; j *= 2, m = p){
22         for(p = 0,i = n-j; i<n;i++) y[p++] = i;
23         for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i]-j;
24         for(i = 0; i < n; i++) wv[i] = x[y[i]];
25         for(i = 0; i < m; i++) wws[i] = 0;
26         for(i = 0; i < n; i++) wws[wv[i]] ++;
27         for(i = 1; i < m; i++) wws[i] += wws[i-1];
28         for(i = n-1; i >= 0; i--) sa[--wws[wv[i]]] = y[i];
29         for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
30             x[sa[i]] = cmp(y,sa[i-1], sa[i],j) ? p-1 : p++;
31     }
32     return ;
33 }
34 
35 int Rank[maxn], height[maxn];
36 void calheight(int *r, int *sa, int n){
37     int i, j, k = 0;
38     for(i = 1; i <= n; i++) Rank[sa[i]] = i;
39     for(i = 0; i < n; height[Rank[i++]] = k)
40         for(k ? k-- : 0, j = sa[Rank[i]-1]; r[i+k] == r[j+k]; k++);
41     return;
42 }
43 
44 bool ok(int x, int len){
45     int mi = sa[1], ma = sa[1];
46     for(int i = 2; i <= len; ++i){
47         if(height[i] < x) mi = ma = sa[i];
48         else{
49             if(sa[i] < mi) mi = sa[i];
50             if(sa[i] > ma) ma = sa[i];
51             //不能 ma-mi >= x，同样a映射的是差值若相等必重叠
52             if(ma - mi > x) return true;
53         }
54     }
55     return false;
56 }
57 
58 int main(){
59     int n, x, y;
60     while(~scanf("%d", &n) && n){
61         //n个数，a[i] 存储a[i+1]-a[i]的值 a的范围是 0 -> n-1
62         scanf("%d", &x);
63         for(int i = 0; i < n-1; ++i) scanf("%d", &y), a[i] = y-x+99, x = y;
64         a[n-1] = 0, n--;
65         da(a, sa, n+1, 555);
66         calheight(a, sa, n);
67         int l = 0, r = n, t = 0; 
68         while(l <= r){
69             int mid = (l+r)>>1;
70             if(ok(mid, n)) t = mid, l = mid+1;
71             else r = mid-1;
72         }
73         //因为a为实际数组的差值，所以用四来判断
74         printf("%d\n", t >= 4 ? t+1 : 0);
75     }
76     return 0;
77 }

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 
  6 const int maxn = 1001 * 100 + 10;
  7 
  8 struct SuffixArray {
  9   int s[maxn];      // 原始字符数组（最后一个字符应必须是0，而前面的字符必须非0）
 10   int sa[maxn];     // 后缀数组
 11   int rank[maxn];   // 名次数组. rank[0]一定是n-1，即最后一个字符
 12   int height[maxn]; // height数组
 13   int t[maxn], t2[maxn], c[maxn]; // 辅助数组
 14   int n; // 字符个数
 15 
 16   void clear() { n = 0; memset(sa, 0, sizeof(sa)); }
 17 
 18   // m为最大字符值加1。调用之前需设置好s和n
 19   void build_sa(int m) {
 20     int i, *x = t, *y = t2;
 21     for(i = 0; i < m; i++) c[i] = 0;
 22     for(i = 0; i < n; i++) c[x[i] = s[i]]++;
 23     for(i = 1; i < m; i++) c[i] += c[i-1];
 24     for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;
 25     for(int k = 1; k <= n; k <<= 1) {
 26       int p = 0;
 27       for(i = n-k; i < n; i++) y[p++] = i;
 28       for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i]-k;
 29       for(i = 0; i < m; i++) c[i] = 0;
 30       for(i = 0; i < n; i++) c[x[y[i]]]++;
 31       for(i = 0; i < m; i++) c[i] += c[i-1];
 32       for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
 33       swap(x, y);
 34       p = 1; x[sa[0]] = 0;
 35       for(i = 1; i < n; i++)
 36         x[sa[i]] = y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k] ? p-1 : p++;
 37       if(p >= n) break;
 38       m = p;
 39     }
 40   }
 41 
 42   void build_height() {
 43     int i, j, k = 0;
 44     for(i = 0; i < n; i++) rank[sa[i]] = i;
 45     for(i = 0; i < n; i++) {
 46       if(k) k--;
 47       int j = sa[rank[i]-1];
 48       while(s[i+k] == s[j+k]) k++;
 49       height[rank[i]] = k;
 50     }
 51   }
 52 };
 53 
 54 const int maxc = 100 + 10; // 串的个数
 55 const int maxl = 1000 + 10; // 每个串的长度
 56 
 57 SuffixArray sa;
 58 int n;
 59 char word[maxl];
 60 int idx[maxn];
 61 int flag[maxc];
 62 
 63 // 子串[L,R) 是否符合要求
 64 bool good(int L, int R) {
 65   memset(flag, 0, sizeof(flag));
 66   if(R - L <= n/2) return false;
 67   int cnt = 0;
 68   for(int i = L; i < R; i++) {
 69     int x = idx[sa.sa[i]];
 70     if(x != n && !flag[x]) { flag[x] = 1; cnt++; }
 71   }
 72   return cnt > n/2;
 73 }
 74 
 75 void print_sub(int L, int R) {
 76   for(int i = L; i < R; i++)
 77     printf("%c", sa.s[i] - 1 + ‘a‘);
 78   printf("\n");
 79 }
 80 
 81 bool print_solutions(int len, bool print) {
 82   int L = 0;
 83   for(int R = 1; R <= sa.n; R++) {
 84     if(R == sa.n || sa.height[R] < len) { // 新开一段
 85       if(good(L, R)) {
 86         if(print) print_sub(sa.sa[L], sa.sa[L] + len); else return true;
 87       }
 88       L = R;
 89     }
 90   }
 91   return false;
 92 }
 93 
 94 void solve(int maxlen) {
 95   if(!print_solutions(1, false))
 96     printf("?\n");
 97   else {
 98     int L = 1, R = maxlen, M;
 99     while(L < R) {
100       M = L + (R-L+1)/2;
101       if(print_solutions(M, false)) L = M;
102       else R = M-1;
103     }
104     print_solutions(L, true);
105   }
106 }
107 
108 // 给字符串加上一个字符，属于字符串i
109 void add(int ch, int i) {
110   idx[sa.n] = i;
111   sa.s[sa.n++] = ch;
112 }
113 
114 int main() {
115   int kase = 0;
116   while(scanf("%d", &n) == 1 && n) {
117     if(kase++ > 0) printf("\n");
118     int maxlen = 0;
119     sa.clear();
120     for(int i = 0; i < n; i++) {
121       scanf("%s", word);
122       int sz = strlen(word);
123       maxlen = max(maxlen, sz);
124       for(int j = 0; j < sz; j++)
125         add(word[j] - ‘a‘ + 1, i);
126       add(100 + i, n); // 结束字符
127     }
128     add(0, n);
129 
130     if(n == 1) printf("%s\n", word);
131     else {
132       sa.build_sa(100 + n);
133       sa.build_height();
134       solve(maxlen);
135     }
136   }
137   return 0;
138 }

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define maxn 2002
 4 
 5 int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
 6 
 7 int cmp(int *r,int a,int b,int l){
 8     return r[a]==r[b]&&r[a+l]==r[b+l];
 9 }
10 
11 void da(int *r,int *sa,int n,int m){
12     int i,j,p,*x=wa,*y=wb,*t;
13     for(i=0;i<m;i++) ws[i]=0;
14     for(i=0;i<n;i++) ws[x[i]=r[i]]++;
15     for(i=1;i<m;i++) ws[i]+=ws[i-1];
16     for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
17     for(j=1,p=1;p<n;j*=2,m=p){
18         for(p=0,i=n-j;i<n;i++) y[p++]=i;
19         for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
20         for(i=0;i<n;i++) wv[i]=x[y[i]];
21         for(i=0;i<m;i++) ws[i]=0;
22         for(i=0;i<n;i++) ws[wv[i]]++;
23         for(i=1;i<m;i++) ws[i]+=ws[i-1];
24         for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
25         for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
26             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
27     }
28     return;
29 }
30 
31 int rank[maxn],height[maxn];
32 void calheight(int *r,int *sa,int n){
33     int i,j,k=0;
34     for(i=1;i<=n;i++) rank[sa[i]]=i;
35     for(i=0;i<n;height[rank[i++]]=k)
36         for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
37     return;
38 }
39 
40 int RMQ[maxn];
41 int mm[maxn];
42 int best[20][maxn];
43 void initRMQ(int n){
44     int i,j,a,b;
45     for(mm[0]=-1,i=1;i<=n;i++)
46         mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
47     for(i=1;i<=n;i++) best[0][i]=i;
48     for(i=1;i<=mm[n];i++)
49         for(j=1;j<=n+1-(1<<i);j++){
50             a=best[i-1][j];
51             b=best[i-1][j+(1<<(i-1))];
52             if(RMQ[a]<RMQ[b]) best[i][j]=a;
53             else best[i][j]=b;
54         }
55     return;
56 }
57 
58 int askRMQ(int a,int b){
59     int t;
60     t=mm[b-a+1];b-=(1<<t)-1;
61     a=best[t][a];b=best[t][b];
62     return RMQ[a]<RMQ[b]?a:b;
63 }
64 
65 int lcp(int a,int b){
66     int t;
67     a=rank[a];b=rank[b];
68     if(a>b) {t=a;a=b;b=t;}
69     return(height[askRMQ(a+1,b)]);
70 }
71 
72 char st[maxn];
73 int r[maxn],sa[maxn];
74 
75 int main(){
76     int i,n,len,k,ans=0,w;
77     scanf("%s",st);
78     len=strlen(st);
79     for(i=0;i<len;i++) r[i]=st[i];
80     r[len]=1;
81     for(i=0;i<len;i++) r[i+len+1]=st[len-1-i];
82     n=len+len+1;
83     r[n]=0;
84     da(r,sa,n+1,128);
85     calheight(r,sa,n);
86     for(i=1;i<=n;i++) RMQ[i]=height[i];
87     initRMQ(n);
88     for(i=0;i<len;i++){
89         k=lcp(i,n-i);
90         if(k*2>ans) ans=k*2,w=i-k;
91         k=lcp(i,n-i-1);
92         if(k*2-1>ans) ans=k*2-1,w=i-k+1;
93     }
94     st[w+ans]=0;
95     printf("%s\n",st+w);
96     return 0;
97 }

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 #define maxn 1000010
 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 
10 int wa[maxn], wb[maxn], wv[maxn], wss[maxn];
11 int c0(int *r, int a, int b) {
12     return r[a] == r[b] && r[a+1] == r[b+1] && r[a+2] == r[b+2];
13 }
14 int c12(int k, int *r, int a, int b) {
15     if(k == 2) return r[a] < r[b] || r[a] == r[b] && c12(1, r, a+1, b+1);
16     else return r[a] < r[b] || r[a] == r[b] && wv[a+1] < wv[b+1];
17 }
18 
19 void sort(int *r, int *a, int *b, int n, int m) {
20     int i;
21     for(i = 0; i < n; i++) wv[i] = r[a[i]];
22     for(i = 0; i < m; i++) wss[i] = 0;
23     for(i = 0; i < n; i++) wss[wv[i]] ++;
24     for(i = 1; i < m; i++) wss[i] += wss[i-1];
25     for(i = n-1; i >= 0; i--) b[--wss[wv[i]]] = a[i];
26     return;
27 }
28 
29 void dc3(int *r, int *sa, int n, int m) {
30     int i, j, *rn = r+n, *san = sa+n, ta = 0, tb = (n+1)/3, tbc=0, p;
31     r[n] = r[n+1] = 0;
32     for(i = 0; i < n; i++) if(i%3 != 0) wa[tbc++] = i;
33     sort(r+2, wa, wb, tbc, m);
34     sort(r+1, wb, wa, tbc, m);
35     sort(r, wa, wb, tbc, m);
36     for(p = 1, rn[F(wb[0])] = 0, i = 1; i < tbc; i++)
37         rn[F(wb[i])] = c0(r, wb[i-1], wb[i]) ? p-1 : p++;
38     if(p < tbc) dc3(rn, san, tbc, p);
39     else for(i = 0; i < tbc; i++) san[rn[i]] = i;
40     for(i = 0; i < tbc; i++) if(san[i] < tb) wb[ta++] = san[i]*3;
41     if(n%3 == 1) wb[ta++] = n-1;
42     sort(r, wb, wa, ta, m);
43     for(i = 0; i < tbc; i++) wv[wb[i]=G(san[i])] = i;
44     for(i = 0, j = 0, p = 0; i < ta && j < tbc; p++)
45         sa[p] = c12(wb[j]%3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
46     for(; i < ta; p++) sa[p] = wa[i++];
47     for(; j < tbc; p++) sa[p] = wb[j++];
48     return;
49 }
50 
51 int rk[3*maxn], height[3*maxn];
52 void calheight(int *r, int *sa, int n) {
53     int i, j, k = 0;
54     for(i = 1; i <= n; i++) rk[sa[i]] = i;
55     for(i = 0; i < n; height[rk[i++]] = k)
56         for(k ? k-- : 0, j = sa[rk[i]-1]; r[i+k] == r[j+k]; k++);
57     return;
58 }
59 
60 char str[maxn];
61 int r[maxn], num[maxn], sa[3*maxn];
62 
63 int main(){
64     while(scanf("%s", str) && str[0] != ‘.‘){
65         int len = strlen(str);
66         for(int i = 0; i < len; ++i){
67             r[i] = str[i]-‘a‘+2;
68         }
69         r[len] = 1;
70         dc3(r, sa, len+1, 30);
71         calheight(r, sa, len);
72         int x = rk[0], ma = maxn;
73         num[x] = len;
74         for(int i = x-1; i >= 0; --i){
75             num[i] = min(ma, height[i+1]);
76             //cout<<"^^^"<<endl;
77         }
78         ma = maxn;
79         for(int i = x+1; i <= len; ++i){
80             num[i] = min(ma, height[i]);
81         }
82         int k = 1;
83         for(int i = 1; i <= len; ++i){
84             //cout << i << "&&" << num[i] << endl;
85             if(len%i == 0 && num[rk[i]] == len-i){
86                 printf("%d\n", len/i);
87                 break;
88             }
89         } 
90     }
91 }