//Accepted 12004 KB 407 ms
/*
source:poj3693
time :20150819
by :songt
*/
/*题解：
搞了一天，总算弄完了
首先，我们来明确一个问题 1.如果一个字符串S由一个子串S1长度为L重复K次得到，那么lcp(0,l)=(K-1)*L;
而如果一个字符串中存在lcp(i,i+L)=m,那么字符串中就存在重复m/L+1次的子串
这个可以画个图看下
下面我们按照论文里的思路，枚举每个循环节的长度L，假设某个长度为L的子串在原字符中出现了两次以上，那么由
容斥原理可知，这段连续重复的子串S一定包括了s[0],s[L],s[2*L],s[3*L],...中的连续的两个，这样我们可以枚举找到
包括最开始的两个是哪两个，假设是s[i*L]和s[(i+1)*L],那么求lcp(i*L,(i+1)*L)=m,由1可知，原字符串中从i*L到(i+1)*L这段
长度为L的子串，一定重复了m/L+1,但是由于i*L和(i+1)*L不一定是重复子串的第一个开始位置，即i*L不一定对应S[0]，所以我们
尝试调整开始的位置，假设i*L对应于S(0,L)中的某个字符，那么lcp(i*L,(i+1)*L)=m中的m就会比(m/L)*m大一点，这一点就是因为i*L
不对应S[0],而对应了S(0,L)中的某个字符造成的，这样我们就可以知道，多匹配的这一点长度就对应（i*L对应于S[k] 0<k<L） k到L这一段
长度，所以应该尝试把i*L向前移动L-m%L个字符(m%L!=0).这样我们就可以求出最大的重复次数。
加入最多只重复了1次也就是没有重复，那么用上面的方法也可以求得。
接下来是求最小字典序的步骤，我们在求最大重复次数的时候，保存对应可能的长度L，那么我们可以从sa[1]到sa[n]枚举，
如果sa[i]和某个长度L能够满足重复次数的要求，那么就得到了答案，枚举中遇到的第一个就是结果，应为sa[1]到sa[n]已经
按照字典序排序
*/
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
;
int wa[imax_n],wb[imax_n],wn[imax_n],wv[imax_n];
int cmp(int *r,int a,int b,int l)
{
return r[a]==r[b] && r[a+l]==r[b+l];
}
void da(int *r,int *sa,int n,int m)
{
int i,j,k,p,*x=wa,*y=wb,*t;
;i<m;i++) wn[i]=;
;i<n;i++) wn[x[i]=r[i]]++;
;i<m;i++) wn[i]+=wn[i-];
;i>=;i--) sa[--wn[x[i]]]=i;
,p=;p<n;j*=,m=p)
{
,i=n-j;i<n;i++) y[p++]=i;
;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;
;i<n;i++) wv[i]=x[y[i]];
;i<m;i++) wn[i]=;
;i<n;i++) wn[wv[i]]++;
;i<m;i++) wn[i]+=wn[i-];
;i>=;i--) sa[--wn[wv[i]]]=y[i];
,x[sa[]]=,i=;i<n;i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
}
return ;
}
int rank[imax_n];
int height[imax_n];
int a[imax_n];
char s[imax_n];
int sa[imax_n];
int n;
void calHeight(int *r,int *sa,int n)
{
;
;i<=n;i++) rank[sa[i]]=i;
;i<n;height[rank[i++]]=k)
,j=sa[rank[i]-];r[i+k]==r[j+k];k++);
return ;
}
int min(int a,int b)
{
return a<b?a:b;
}
];
int mm[imax_n];
void initRMQ(int n,int b[])
{
mm[]=-;
;i<=n;i++)
{
mm[i]=((i&(i-))==)?mm[i-]+:mm[i-];
dp[i][]=b[i];
}
;j<=mm[n];j++)
{
;i+(<<j)-<=n;i++)
{
dp[i][j]=min(dp[i][j-],dp[i+(<<(j-))][j-]);
}
}
}
int rmq(int x,int y)
{
x=rank[x];
y=rank[y];
if (x>y)
{
int tmp=x;
x=y;
y=tmp;
}
x++;
];
<<k)+][k]);
}
vector<int > vec;
void Deal()
{
n=strlen(s);
;i<n;i++)
{
a[i]=(int )s[i];
}
a[n]=;
da(a,sa,n+,);
calHeight(a,sa,n);
initRMQ(n,height);
vec.clear();
;
;l<=n/;l++) //枚举循环节的长度
{
;i+l<n;i+=l) //找对应子串S第一个循环节和第二个循环节的位置
{
int length=rmq(i,i+l); //求出重复的次数
;
int newpos=i-(l-length%l);
&& length%l && rmq(newpos,newpos+l)>length) times++; //尝试更新结果
if (times>max_times)
{
vec.clear();
vec.push_back(l);
max_times=times;
}
else if (times==max_times)
{
vec.push_back(l);
}
}
}
sort(vec.begin(),vec.end());
int cnt=unique(vec.begin(),vec.end())-vec.begin();
//printf("max_times=%d\n",max_times);
//for (int i=0;i<cnt;i++)
//{
// printf("length=%d\n",vec[i]);
//}
int start,length;
//printf("size=%d\n",vec.size());
;
;i<=n && !flag;i++)
{
;j<cnt && !flag;j++)
{
)*vec[j])
{
start=sa[i];
length=vec[j]*max_times;
flag=;
}
}
}
//printf("start=%d length=%d\n",start,length);
for (int i=start;i<start+length;i++)
printf("%c",s[i]);
printf("\n");
}
int main()
{
int T;
;
)
{
) break;
printf("Case %d: ",++t);
Deal();
}
;
}