题意：求字典序最小且重复次数最多的连续重复子串
思路：
枚举循环节长度i，再枚举起始位置（0开始，每次加i），求出循环次数
这里有一个关键：枚举的起始位置不一定是答案所在的位置
比如：c a b a b a b
枚举循环节长度为2，起始位置2时
根据RMQ可O（1）求出suffix(2)和suffix(2+2)的lcp=3,循环次数为lcp/i+1=2
但是我们可以看到，正确答案为循环节长度2，起始位置1，循环次数3
为了解决这个问题，我们要考虑lcp/i不能整除的情况，这就意味着所有的lcp未全部用上，这个时候如果把起始位置往前挪一点，有可能会把这部分也利用上
(代码模板有点问题)
#include"cstdio" #include"queue" #include"cmath" #include"stack" #include"iostream" #include"algorithm" #include"cstring" #include"queue" #include"map" #include"set" #include"vector" #define ll long long #define mems(a,b) memset(a,b,sizeof(a)) #define ls pos<<1 #define rs pos<<1|1 using namespace std; const int MAXE = 500050; const int MAXN = 100005; const int maxn = 1e5+5; const int INF = 0x3f3f3f3f; int sa[MAXN]; int X[MAXN],Y[MAXN],radix[300],trank[MAXN]; int _rank[MAXN]; void get_sa(int *r,int *sa,int n,int m){ int i,j,p,*Rank=X,*tsa=Y,*t; for (i=0;i<m;i++) radix[i]=0; for (i=0;i<n;i++) radix[Rank[i]=r[i]]++; for (i=1;i<m;i++) radix[i]+=radix[i-1]; for (i=n-1;i>=0;i--) sa[--radix[Rank[i]]]=i; for (j=1,p=1;p<n;j*=2,m=p) { for (p=0,i=n-j;i<n;i++) tsa[p++]=i; for (i=0;i<n;i++) if (sa[i]>=j) tsa[p++]=sa[i]-j; for (i=0;i<n;i++) trank[i]=Rank[tsa[i]]; for (i=0;i<m;i++) radix[i]=0; for (i=0;i<n;i++) radix[trank[i]]++; for (i=1;i<m;i++) radix[i]+=radix[i-1]; for (i=n-1;i>=0;i--) sa[--radix[trank[i]]]=tsa[i]; for (t=Rank,Rank=tsa,tsa=t,p=1,Rank[sa[0]]=0,i=1;i<n;i++){ if(tsa[sa[i-1]]==tsa[sa[i]]&&tsa[sa[i-1]+j]==tsa[sa[i]+j]) Rank[sa[i]]=p-1; else Rank[sa[i]]=p++; } } } int height[MAXN]; void get_height(int *r,int *sa,int n){ int i,j=0,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 ++); } int dp[MAXN][20]; void make_rmq(int N){ for(int i=1;i<=N;i++) dp[i][0]=height[i]; for(int j=1;(1<<j)<=N;j++) for(int i=1;i+(1<<j)-1<N;i++) dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } int query(int l,int r){ l=_rank[l]; r=_rank[r]; if(l>r)swap(l,r); l++; int k=(int)(log((r-l+1)*1.0)/log(2.0)); return min(dp[l][k],dp[r-(1<<k)+1][k]); } int p=1; char arr[MAXN]; int r[MAXN]; int main(){ //freopen("in.txt","r",stdin); while(scanf("%s",arr)){ if(arr[0]=='#') break; int n=strlen(arr); for(int i=0;i<n;i++) r[i]=arr[i]-'a'+1; r[n]=0; get_sa(r,sa,n+1,150); get_height(r,sa,n); make_rmq(n+1); int times=0,cnt=0; int len[MAXN]; for(int i=1;i<n;i++){ for(int j=0;j+i<n;j+=i){ int lcp=query(j,j+i); int t=lcp/i+1; int k=j-(i-lcp%i); if(k>=0&&(lcp%i)){ if(query(k,k+i)>=lcp) t++; } if(t>times){ times=t; cnt=0; len[cnt++]=i; } else if(times==t) len[cnt++]=i; } } /*cout<<times<<endl; for(int i=0;i<cnt;i++) cout<<len[i]<<' '; cout<<endl;*/ int f=0,l,pos; for(int i=1;i<=n;i++){ if(f) break; for(int j=0;j<cnt;j++){ l=len[j]; if(query(sa[i],sa[i]+l)>=(times-1)*l){ f=1; pos=sa[i]; break; } } } printf("Case %d: ",p++); for(int i=0;i<l*times;i++) cout<<arr[i+pos]; cout<<endl; } return 0; }