呵呵呵呵呵呵呵呵呵呵，sb（神犇）题看了一天，还是不懂
题目要求的是最多重复的，那么就来找重复的，可以先枚举一个重复的单元（比如ababab，就枚举ab）的长度，
然后再原串中，会有ch[0],ch[L],c[2*L],,,,,这些，如果重复的话肯定是会有ch[i*L]==ch[(i+1)*L]的，那么我们枚举这个东西。
在找到之后，需要做的就是找ch[(i+1)*L]之后可以有多长重复 L1，以及ch[i*L]之前有多少重复 L2，这个问题用后缀数组的height处理出的RMQ解决（呵呵呵），这一步貌似是叫求两个后缀的最长公共前缀。。。（对余ch[i*L]往前的，就把串反过来搞），然后答案就是(L1+L2)/L+1。
然而这个恶心题还要求最小字典序。。。。那么考虑，另外寻找重复部分的开头，我们知道，已经找出了重复串的长度，那么在这里面的任意位置都是满足重复这个性质的，所以考虑(L1+L2)%L（长度不及L的部分，可以画图看一下），然后在搞一个ST表来记录区间的rank，然后在 i*L-L2 到 i*L-L2+(L1+L2)%L查询最小的rank就好。。
（本蒟蒻就会这么多，大神勿喷2333）
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define N 100005 5 #define LL long long 6 #define inf 0x3f3f3f3f 7 using namespace std; 8 int n,mx,ans,ansl,ansr; 9 int bin[30],Log[100005]; 10 int mn[100005][17]; 11 char ch[100005]; 12 void rmq(int mn[N][17], int *a) 13 { 14 for (int i=1; i<=n; i++) mn[i][0]=a[i]; 15 for (int i=1; i<=Log[n]; i++) 16 for (int j=1; j<=n; j++) 17 if (j+bin[i]-1<=n) 18 mn[j][i]=min(mn[j][i-1],mn[j+bin[i-1]][i-1]); 19 else break; 20 } 21 struct Suffix{ 22 int k,p,q; 23 int rk[2][N],sa[2][N],v[N],a[N]; 24 int h[N],mn[N][17]; 25 void clear() 26 { 27 memset(a,0,sizeof(a)); 28 memset(v,0,sizeof(v)); 29 memset(rk,0,sizeof(rk)); 30 } 31 void cal_sa(int *sa, int *rk, int *SA, int *RK) 32 { 33 for (int i=1; i<=n; i++) v[rk[sa[i]]]=i; 34 for (int i=n; i>=1; i--) 35 if (sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k; 36 for (int i=n-k+1; i<=n; i++) SA[v[rk[i]]--]=i; 37 for (int i=1; i<=n; i++) 38 RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i-1]]!=rk[SA[i]] || rk[SA[i-1]+k]!=rk[SA[i]+k]); 39 } 40 void get_sa() 41 { 42 p=0,q=1; 43 for (int i=1; i<=n; i++) v[a[i]]++; 44 for (int i=1; i<=30; i++) v[i]+=v[i-1]; 45 for (int i=1; i<=n; i++) sa[p][v[a[i]]--]=i; 46 for (int i=1; i<=n; i++) 47 rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]); 48 for (k=1; k<n; k<<=1,swap(p,q)) cal_sa(sa[p],rk[p],sa[q],rk[q]); 49 } 50 void get_height() 51 { 52 k=0; 53 for (int i=1; i<=n; i++) 54 { 55 if (rk[p][i]==1) h[1]=0; 56 else{ 57 int j=sa[p][rk[p][i]-1]; 58 while (a[i+k]==a[j+k]) k++; 59 h[rk[p][i]]=k; 60 if (k>0) k--; 61 } 62 } 63 } 64 void pre() 65 { 66 get_sa(); get_height(); rmq(mn,h); 67 } 68 int lcp(int x, int y) 69 { 70 x=rk[p][x],y=rk[p][y]; 71 if (x>y) swap(x,y); 72 x++; 73 int t=Log[y-x+1]; 74 return min(mn[x][t],mn[y-bin[t]+1][t]); 75 } 76 }c[2]; 77 int query(int x, int y) 78 { 79 int t=Log[y-x+1]; 80 return min(mn[x][t],mn[y-bin[t]+1][t]); 81 } 82 void solve(int L) 83 { 84 int l=0,r=0,t; 85 for (int i=1; i+L<=n; i+=L) 86 if (ch[i]==ch[i+L]) 87 { 88 r=c[0].lcp(i,i+L),l=c[1].lcp(n-i+2,n-i-L+2); 89 if ((l+r)/L+1>mx) 90 mx=(l+r)/L+1,ans=inf; 91 if ((l+r)/L+1==mx) 92 { 93 t=query(i-l,i-l+(l+r)%L); 94 if (t<ans) 95 { 96 ans=t; 97 ansl=c[0].sa[c[0].p][t],ansr=ansl+mx*L-1; 98 } 99 } 100 } 101 } 102 int main() 103 { 104 bin[0]=1; for (int i=1; i<=20; i++) bin[i]=bin[i-1]<<1; 105 Log[0]=-1; for (int i=1; i<=100000; i++) Log[i]=Log[i/2]+1; 106 int txt=0; 107 while (scanf("%s",ch+1)) 108 { 109 if (ch[1]=='#') break; 110 printf("Case %d: ",++txt); 111 c[0].clear(); c[1].clear(); 112 n=strlen(ch+1); 113 for (int i=1; i<=n; i++) c[0].a[i]=ch[i]-'a'+1; 114 for (int i=1; i<=n; i++) c[1].a[i]=ch[n-i+1]-'a'+1; 115 c[0].pre(); c[1].pre(); 116 rmq(mn,c[0].rk[c[0].p]); 117 mx=1; ans=inf; 118 for (int i=1; i<=n; i++) 119 if (c[0].rk[c[0].p][i]<ans) 120 ans=c[0].rk[c[0].p][i],ansl=ansr=i; 121 for (int i=1; i<=n; i++) solve(i); 122 for (int i=ansl; i<=ansr; i++) 123 putchar(ch[i]); 124 puts(""); 125 } 126 return 0; 127 }