【POJ 3693】Maximum repetition substring

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<string>
  4 #include<iostream>
  5 #include<algorithm>
  6 using namespace std;
  7 const int MAX_CHAR = 128;
  8 const int MAXN     = 100000 + 5;
  9 const int INF      = 2e9 + 7;
 10 int lg[MAXN], f[MAXN], g[MAXN];
 11 struct suff_string
 12 {
 13     int n, m;
 14     int x[MAXN] , y[MAXN] , c[MAXN] ;
 15     int SA[MAXN], rak[MAXN], height[MAXN];
 16     int st[17][MAXN];
 17     void build_SA(char *s)
 18     {
 19         n = strlen(s + 1);
 20         m = MAX_CHAR;
 21         for (int i = 1; i <= 100000; i++)
 22             x[i] = y[i] = c[i] = SA[i]=rak[i]=height[i]=0;
 23         for (int i = 1; i <= n; i++)
 24             SA[i] = rak[i] = height[i] = 0;
 25         for (int i = 1; i <= n; i++)
 26             ++c[x[i] = s[i]];
 27         for (int i = 2; i <= m; i++)
 28             c[i] += c[i - 1];
 29         for (int i = n; i >= 1; i--)
 30             SA[c[x[i]]--] = i;
 31         for (int k = 1; k <= n; k <<= 1)
 32         {
 33             int num = 0;
 34             for (int i = n - k + 1; i <= n; i++)    y[++num] = i;
 35             for (int i = 1; i <= n; i++)
 36                 if (SA[i] > k)
 37                     y[++num] = SA[i] - k;
 38             for (int i = 1; i <= m; i++)
 39                 c[i] = 0;
 40             for (int i = 1; i <= n; i++)
 41                 c[x[i]]++;
 42             for (int i = 2; i <= m; i++)
 43                 c[i] += c[i - 1];
 44             for (int i = n; i >= 1; i--)
 45                 SA[c[x[y[i]]]--] = y[i], y[i] = 0;
 46             swap(x, y);
 47             x[SA[1]] = 1; num = 1;
 48             for (int i = 2; i <= n; i++)
 49                 x[SA[i]] = (y[SA[i]] == y[SA[i - 1]] && y[SA[i] + k] == y[SA[i - 1] + k]) ? num : ++num;
 50             if (num == n) break;
 51             m = num;
 52         }
 53         for (int i = 1; i <= n; i++)
 54             rak[SA[i]] = i;
 55         return;
 56     }
 57     void get_height(char *s)
 58     {
 59         int k = 0;
 60         for (int i = 1; i <= n; i++) {
 61             if (k) k--;
 62             int j = SA[rak[i] - 1];
 63             while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
 64             height[rak[i]] = k;
 65         }
 66     }
 67 
 68     void build_ST()
 69     {
 70         memset(st, 0, sizeof(st));
 71         for (int i = 1; i <= n; i++)
 72             st[0][i] = height[i];
 73         for (int i = 1; i <= 16; i++)
 74             for (int j = 1; j <= n; j++)
 75                 st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
 76     }
 77     int query(int l, int r)
 78     {
 79         l = rak[l], r = rak[r];
 80         if (l > r)    swap(l, r); l++;
 81         int t = lg[r + 1 - l];
 82         return min(st[t][l], st[t][r - (1 << t) + 1]);
 83     }
 84 }A;
 85 char s[MAXN];
 86 int _ = 0;
 87 int ans[MAXN];
 88 bool solve()
 89 {
 90     scanf("%s", s + 1);
 91     if (s[1] == ‘#‘)
 92         return 0;
 93     A.build_SA(s);  A.get_height(s);  A.build_ST();
 94     int n = A.n;
 95     int mx = -1;
 96     int len = 0;
 97     for (int i = 1; i < n; i++)
 98     {
 99         for (int j = 1; j+i <= n; j += i)
100         {
101             int k = A.query(j,j+i);
102             int t = k / i +1;
103             int left = i - (k%i);
104             int head =j- left;
105             if (head >= 1 && A.query(head, head + i)>=left) t++;
106             if (t > mx)
107             {
108                 mx = t;
109                 ans[0] = 0;
110             }
111             if (t == mx)
112             {
113                 ans[++ans[0]] = i;
114             }
115         }
116     }
117     int head=INF;
118     int flag = 0;
119     for (int i = 1; i <= n; i++)
120     {
121         for (int j = 1; j <= ans[0]; j++)
122         {
123             int l = ans[j];
124             if (A.query(A.SA[i], A.SA[i] + l) >= (mx - 1)*l)
125             {
126                 len = l;
127                 head = A.SA[i];
128                 flag = 1;
129                 break;
130             }
131         }
132         if (flag)    break;
133     }
134     printf("Case %d: ", ++_);
135     for (int i = 0; i <mx*len; i++)
136         printf("%c", s[head+i]);
137     printf("\n");
138     return 1;
139 }
140 int main()
141 {
142     int T;
143     for (int i = 2; i <= 100000; i++) lg[i] = lg[i >> 1] + 1;
144     scanf("%d", &T);
145     getchar();
146     while (T--  && solve())
147     {
148 
149     }
150     return 0;
151 }