POJ_3693
这个题目和SPOJ_687差不多，基本的思路可以参考罗穗骞的论文和我的SPOJ_687的题解http://www.cnblogs.com/staginner/archive/2012/02/06/2340521.html。
对于字典序最小这一条件，我没有想到太好的解决策略，只是默认r[L*i]在第一循环节内，然后向前枚举第一个循环节的首字符的位置，如果此时repetition number和max相等，那么就将这个字符串记录下来，如果比max大，就更新max，并把记录的可能的解清零后再将这个字符串记录下来，如果比max小就直接break，而不用再继续向前枚举第一个循环节首字符的位置了，因为当前的这对字符不能匹配，是不可能包含在解之中的。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 100010
#define INF 0x3f3f3f3f
char b[MAXD];
int N, r[MAXD], sa[MAXD], rank[MAXD], height[MAXD], wa[MAXD], wb[MAXD], ws[MAXD], wv[MAXD];
int best[20][MAXD], mm[MAXD], len[MAXD], first[MAXD], P;
void init()
{
int i;
for(i = 0; b[i]; i ++)
r[i] = b[i];
r[N = i] = 0;
}
int cmp(int *p, int x, int y, int l)
{
return p[x] == p[y] && p[x + l] == p[y + l];
}
int cmp1(const void *_p, const void *_q)
{
int i, *p = (int *)_p, *q = (int *)_q;
for(i = 0; i < len[*p] && i < len[*q]; i ++)
{
if(r[first[*p] + i] < r[first[*q] + i])
return -1;
else if(r[first[*p] + i] > r[first[*q] + i])
return 1;
}
if(i == len[*p])
return -1;
return 1;
}
void da(int n, int m)
{
int i, j, p, *x = wa, *y = wb, *t;
memset(ws, 0, sizeof(ws[0]) * m);
for(i = 0; i < n; i ++)
++ ws[x[i] = r[i]];
for(i = 1; i < m; i ++)
ws[i] += ws[i - 1];
for(i = n - 1; i >= 0; i --)
sa[-- ws[x[i]]] = i;
for(j = p = 1; p < n; j *= 2, m = p)
{
for(p = 0, i = n - j; i < n; i ++)
y[p ++] = i;
for(i = 0; i < n; i ++)
if(sa[i] >= j)
y[p ++] = sa[i] - j;
for(i = 0; i < n; i ++)
wv[i] = x[y[i]];
memset(ws, 0, sizeof(ws[0]) * m);
for(i = 0; i < n; i ++)
++ ws[wv[i]];
for(i = 1; i < m; i ++)
ws[i] += ws[i - 1];
for(i = n - 1; i >= 0; i --)
sa[-- ws[wv[i]]] = y[i];
for(t = x, x = y, y = t, x[sa[0]] = 0, i = p = 1; i < n; i ++)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p ++;
}
}
void calheight(int n)
{
int i, j, k = 0;
for(i = 1; i <= n; i ++)
rank[sa[i]] = i;
for(i = 0; i < n; height[rank[i ++]] = k)
for(k ? -- k : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k ++);
}
void initRMQ(int n)
{
int i, j, x, y;
for(mm[0] = -1, i = 1; i <= n; i ++)
mm[i] = (i & (i - 1)) == 0 ? mm[i - 1] + 1 : mm[i - 1];
for(i = 1; i <= n; i ++)
best[0][i] = i;
for(i = 1; i <= mm[n]; i ++)
for(j = 1; j <= n - (1 << i) + 1; j ++)
{
x = best[i - 1][j];
y = best[i - 1][j + (1 << (i - 1))];
best[i][j] = height[x] < height[y] ? x : y;
}
}
int askRMQ(int x, int y)
{
int t = mm[y - x + 1];
y = y - (1 << t) + 1;
x = best[t][x];
y = best[t][y];
return height[x] < height[y] ? height[x] : height[y];
}
int calculate(int x, int y)
{
int t;
x = rank[x], y = rank[y];
if(x > y)
t = x, x = y, y = t;
++ x;
return askRMQ(x, y);
}
void printresult(int max)
{
int i, j, k;
if(max == 1)
{
k = INF;
for(i = 0; i < N; i ++)
if(r[i] < k)
k = r[i];
printf("%c\n", k);
}
else
{
for(i = 0; i < P; i ++)
ws[i] = i;
qsort(ws, P, sizeof(ws[0]), cmp1);
for(i = 0, k = ws[0]; i < len[k]; i ++)
printf("%c", r[first[k] + i]);
printf("\n");
}
}
void solve()
{
int i, j, k, p, max = 1, ans;
da(N + 1, 128);
calheight(N);
initRMQ(N);
for(i = 1; i < N; i ++)
for(j = 0; j + i < N; j += i)
{
ans = calculate(j, j + i);
k = j - (i - ans % i);
ans = ans / i + 1;
if(ans < max - 1 || (ans == max - 1 && calculate(k, k + i) < i))
continue;
for(k = ans == max - 1 ? k : j; j - k < i; k --)
{
ans = calculate(k, k + i);
ans = ans / i + 1;
if(ans < max)
break;
if(ans > max)
{
max = ans;
P = 0;
}
first[P] = k, len[P] = ans * i;
++ P;
}
}
printresult(max);
}
int main()
{
int t = 0;
for(;;)
{
scanf("%s", b);
if(b[0] == '#')
break;
printf("Case %d: ", ++ t);
init();
solve();
}
return 0;
}