【2012 百度之星资格赛 H:用户请求中的品牌】

H:用户请求中的品牌

时间限制:: 1000ms
内存限制:: 65536kB

描述

馅饼同学是一个在百度工作，做用户请求（query）分析的同学，他在用户请求中经常会遇到一些很奇葩的词汇。在比方说“johnsonjohnson”、“duckduck”，这些词汇虽然看起来是一些词汇的单纯重复，但是往往都是一些特殊品牌的词汇，不能被拆分开。为了侦测出这种词的存在，你今天需要完成我给出的这个任务——“找出用户请求中循环节最多的子串”。

输入

输入数据包括多组，每组为一个全部由小写字母组成的不含空格的用户请求（字符串），占一行。用户请求的长度不大于100,000。
最后一行输入为#，作为结束的标志。

输出

对于每组输入，先输出这个组的编号（第n组就是输出“Case n:”）；然后输出这组用户请求中循环节最多的子串。如果一个用户请求中有两个循环节数相同的子串，请选择那个字典序最小的。

样例输入

ilovejohnsonjohnsonverymuch
duckduckgo
aaabbbcccisagoodcompany
#

样例输出

Case 1: johnsonjohnson
Case 2: duckduck
Case 3: aaa

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stdlib.h>
  4 #define MAXD 100010
  5 #define INF 0x3f3f3f3f
  6 char b[MAXD];
  7 int N, r[MAXD], sa[MAXD], rank[MAXD], height[MAXD], wa[MAXD], wb[MAXD], ws[MAXD], wv[MAXD];
  8 int best[20][MAXD], mm[MAXD], len[MAXD], first[MAXD], P;
  9 void init()
 10 {
 11     int i;
 12     for(i = 0; b[i]; i ++)
 13         r[i] = b[i];
 14     r[N = i] = 0;
 15 }
 16 int cmp(int *p, int x, int y, int l)
 17 {
 18     return p[x] == p[y] && p[x + l] == p[y + l];
 19 }
 20 int cmp1(const void *_p, const void *_q)
 21 {
 22     int i, *p = (int *)_p, *q = (int *)_q;
 23     for(i = 0; i < len[*p] && i < len[*q]; i ++)
 24     {
 25         if(r[first[*p] + i] < r[first[*q] + i])
 26             return -1;
 27         else if(r[first[*p] + i] > r[first[*q] + i])
 28             return 1;
 29     }
 30     if(i == len[*p])
 31         return -1;
 32     return 1;
 33 }
 34 void da(int n, int m)
 35 {
 36     int i, j, p, *x = wa, *y = wb, *t;
 37     memset(ws, 0, sizeof(ws[0]) * m);
 38     for(i = 0; i < n; i ++)
 39         ++ ws[x[i] = r[i]];
 40     for(i = 1; i < m; i ++)
 41         ws[i] += ws[i - 1];
 42     for(i = n - 1; i >= 0; i --)
 43         sa[-- ws[x[i]]] = i;
 44     for(j = p = 1; p < n; j *= 2, m = p)
 45     {
 46         for(p = 0, i = n - j; i < n; i ++)
 47             y[p ++] = i;
 48         for(i = 0; i < n; i ++)
 49             if(sa[i] >= j)
 50                 y[p ++] = sa[i] - j;
 51         for(i = 0; i < n; i ++)
 52             wv[i] = x[y[i]];
 53         memset(ws, 0, sizeof(ws[0]) * m);
 54         for(i = 0; i < n; i ++)
 55             ++ ws[wv[i]];
 56         for(i = 1; i < m; i ++)
 57             ws[i] += ws[i - 1];
 58         for(i = n - 1; i >= 0; i --)
 59             sa[-- ws[wv[i]]] = y[i];
 60         for(t = x, x = y, y = t, x[sa[0]] = 0, i = p = 1; i < n; i ++)
 61             x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p ++;
 62     }
 63 }
 64 void calheight(int n)
 65 {
 66     int i, j, k = 0;
 67     for(i = 1; i <= n; i ++)
 68         rank[sa[i]] = i;
 69     for(i = 0; i < n; height[rank[i ++]] = k)
 70         for(k ? -- k : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k ++);
 71 }
 72 void initRMQ(int n)
 73 {
 74     int i, j, x, y;
 75     for(mm[0] = -1, i = 1; i <= n; i ++)
 76         mm[i] = (i & (i - 1)) == 0 ? mm[i - 1] + 1 : mm[i - 1];
 77     for(i = 1; i <= n; i ++)
 78         best[0][i] = i;
 79     for(i = 1; i <= mm[n]; i ++)
 80         for(j = 1; j <= n - (1 << i) + 1; j ++)
 81         {
 82             x = best[i - 1][j];
 83             y = best[i - 1][j + (1 << (i - 1))];
 84             best[i][j] = height[x] < height[y] ? x : y;
 85         }
 86 }
 87 int askRMQ(int x, int y)
 88 {
 89     int t = mm[y - x + 1];
 90     y = y - (1 << t) + 1;
 91     x = best[t][x];
 92     y = best[t][y];
 93     return height[x] < height[y] ? height[x] : height[y];
 94 }
 95 int calculate(int x, int y)
 96 {
 97     int t;
 98     x = rank[x], y = rank[y];
 99     if(x > y)
100         t = x, x = y, y = t;
101     ++ x;
102     return askRMQ(x, y);
103 }
104 void printresult(int max)
105 {
106     int i, j, k;
107     if(max == 1)
108     {
109         k = INF;
110         for(i = 0; i < N; i ++)
111             if(r[i] < k)
112                 k = r[i];
113         printf("%c\n", k);
114     }
115     else
116     {
117         for(i = 0; i < P; i ++)
118             ws[i] = i;
119         qsort(ws, P, sizeof(ws[0]), cmp1);
120         for(i = 0, k = ws[0]; i < len[k]; i ++)
121             printf("%c", r[first[k] + i]);
122         printf("\n");
123     }
124 }
125 void solve()
126 {
127     int i, j, k, p, max = 1, ans;
128     da(N + 1, 128);
129     calheight(N);
130     initRMQ(N);
131     for(i = 1; i < N; i ++)
132         for(j = 0; j + i < N; j += i)
133         {
134             ans = calculate(j, j + i);
135             k = j - (i - ans % i);
136             ans = ans / i + 1;
137             if(ans < max - 1 || (ans == max - 1 && calculate(k, k + i) < i))
138                 continue;
139             for(k = ans == max - 1 ? k : j; j - k < i; k --)
140             {
141                 ans = calculate(k, k + i);
142                 ans = ans / i + 1;
143                 if(ans < max)
144                     break;
145                 if(ans > max)
146                 {
147                     max = ans;
148                     P = 0;
149                 }
150                 first[P] = k, len[P] = ans * i;
151                 ++ P;
152             }
153         }
154     printresult(max);
155 }
156 int main()
157 {
158     int t = 0;
159     for(;;)
160     {
161         scanf("%s", b);
162         if(b[0] == '#')
163             break;
164         printf("Case %d: ", ++ t);
165         init();
166         solve();
167     }
168     return 0;
169 }