重复次数最多的字串，我们可以枚举循环节的长度。
然后正反两次LCP，然后发现如果长度%L有剩余的情况时，答案是在一个区间内的。
所以需要找到区间内最小的rk值。
两个后缀数组，四个ST表，$\Theta(n\log n)$
就可以解决了
空间卡死了，瞎晶胞卡过去了。
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define ll long long
#define mp make_pair
#define maxn 200010
#define inf 0x3f3f3f3f int _log[maxn],kas=0; struct Suffix_Array{
int s[maxn];
int cnt[maxn],sa[maxn],tmp[maxn],rk[maxn],h[maxn];
int st[2][maxn][18];
void build(int n,int m)
{
s[n]=0; n++; int i,j,k;
F(i,0,n+2) sa[i]=tmp[i]=rk[i]=h[i]=0;
F(i,0,m-1) cnt[i]=0;
F(i,0,n-1) cnt[rk[i]=s[i]]++;
F(i,1,m-1) cnt[i]+=cnt[i-1];
F(i,0,n-1) sa[--cnt[rk[i]]]=i;
for (k=1;k<=n;k<<=1)
{
F(i,0,n-1)
{
int j=sa[i]-k;
if (j<0) j+=n;
tmp[cnt[rk[j]]++]=j;
}
sa[tmp[cnt[0]=0]]=j=0;
F(i,1,n-1)
{
if (rk[tmp[i]]!=rk[tmp[i-1]]||rk[tmp[i]+k]!=rk[tmp[i-1]+k]) cnt[++j]=i;
sa[tmp[i]]=j;
}
memcpy(rk,sa,n*sizeof(int));
memcpy(sa,tmp,n*sizeof(int));
if (j>=n-1) break;
}
for (int i=k=0;i<n;h[rk[i++]]=k)
for (k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
F(i,0,n-1) st[0][i][0]=h[i];
F(i,1,17) F(j,0,n-(1<<i)) st[0][j][i]=min(st[0][j][i-1],st[0][j+(1<<(i-1))][i-1]);
F(i,0,n-1) st[1][i][0]=rk[i];
F(i,1,17) F(j,0,n-(1<<i)) st[1][j][i]=min(st[1][j][i-1],st[1][j+(1<<(i-1))][i-1]);
}
int query(int id,int l,int r)
{
int k=_log[r-l+1];
return min(st[id][l][k],st[id][r-(1<<k)+1][k]);
}
int lcp(int a,int b)
{
int aa=rk[a],bb=rk[b];
return query(0,min(aa,bb)+1,max(aa,bb));
}
}SA,SB; int ansl,ansr,mx,ans,n,minn;char s[maxn]; void solve(int L)
{
for (int i=0;i+L<n;i+=L)
if (s[i]==s[i+L])
{
int l=SA.lcp(i+1,i+L+1),r=SB.lcp(n-i-1,n-i-L-1);
if (l+r<L) continue;
if ((l+r)/L+1>mx) mx=(l+r)/L+1,ans=inf;
if ((l+r)/L+1==mx)
{
int tmp=SA.query(1,i-r+1,i-r+1+(l+r)%L);
if (tmp<ans)
{
ans=tmp;
ansl=SA.sa[tmp]; ansr=ansl+mx*L-1;
}
}
}
} int main()
{
F(i,2,maxn-1) _log[i]=_log[i>>1]+1;
while (scanf("%s",s)!=EOF&&s[0]!='#')
{
ansl=ansr=0,mx=0;minn=inf;
printf("Case %d: ",++kas);
mx=0;
n=strlen(s);
F(i,0,n-1)
{
SA.s[i]=s[i]-'a'+1;
SB.s[i]=s[n-i-1]-'a'+1;
minn=min(minn,(int)s[i]);
}
SA.s[n]=SB.s[n]=0;
SA.build(n,30); SB.build(n,30);
for (int i=1;i<=n;++i) solve(i);
if (mx==0) printf("%c\n",minn);
else
{
F(i,ansl,ansr) printf("%c",s[i]);
printf("\n");
}
}
}