学步园

ccabababc
daabbccaa
#

Case 1: ababab
Case 2: aa

题意：

首先定义了一个字符串的重复度。即一个字符串由一个子串重复k次构成。那么最大的k即是该字符串的重复度。比如

abababab度为4.abc度为1。现在给你一个长度不超过10^5的字符串要你找出它的度数最大的子串。如果有多解。找出字典序最小的一个。

思路：

容易想到的就是枚举长度为L，然后看长度为L的字符串最多连续出现几次。
长度为L的串重复出现，那么st[0],st[l],st[2*l]……st[k*l]中肯定有两个连续的出现在字符串中。不然肯定长度不超过2*L啊。那么我们就枚举连续的两个，然后从这两个字符前后匹配，看最多能匹配多远。
即以st[i*l],st[i*l+l]前后匹配，这里是通过查询suffix(i*l),suffix(i*l+l)的最长公共前缀
通过rank值能找到i*l,与i*l+l的排名，我们要查询的是这段区间的height的最小值，通过RMQ预处理
达到查询为0(1)的复杂度，设LCP长度为M, 则答案显然为M / L + 1, 但这只是以i*l和i*l+l为起点的情况, 不过有一点是可以确定的。如果目标子串包含了i*l和i*l+l。那么i*l一定是和i*l+l匹配的。因为目标串中p一定和p+l匹配。这样才能满足子串长度为l。先在要解决的就是起点不在这两个位置上怎么办了。 得到M/L+1我们可以试着把答案变大。如果M%L!=0我们可以把长度补齐到L的整数倍。即在前面增加(L-M%L)的字符.看能不能使答案变大。为什么这样做是可以的呢？因为我们要使啊、答案变大往后扩展肯定不行了。因为后面已经不匹配了。但是我们为什么扩展(L-M%L)这么多就行了呢。比这个小肯定是不行的。因为还是没到L的整数倍。比这个多能行的话。去这个值一定能行。因为p是和p+L匹配的。既然取得比这个多。大不了往右平移几个还是能使M%L得到匹配。那为什么只扩展一个长度L。不扩展多个呢。因为你是枚举每个i*l和i*l+l。你扩展2个或两个以上就是前面的i*l和i*l+l的情况了。这一步完成后我们只能得到度数最大长度可能的取值。剩下的工作就是找字典序最小了。通过sa数组进行枚举，取到的第一组，肯定是字典序最小的。

详细见代码：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int sa[maxn],T1[maxn],T2[maxn],he[maxn],rk[maxn],ct[maxn];
int rmq[25][maxn],lg[maxn],alen[maxn],ptr;
int n,m,ans;
char txt[maxn],atx[maxn];
void rmq_init()
{
    int i,j;
    for(i=0;i<n;i++)
        rmq[0][i]=he[i];
    for(i=1;i<=lg[n];i++)
        for(j=0;j+(1<<i)-1<n;j++)
            rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
int rmq_min(int l,int r)
{
    int tmp=lg[r-l+1];
    return min(rmq[tmp][l],rmq[tmp][r-(1<<tmp)+1]);
}
void prermq()
{
    int  i;
    lg[0]=-1;
    for(i=1;i<maxn;i++)
        lg[i]=lg[i>>1]+1;
}
void getsa(char *st)
{
    int i,k,p,*x=T1,*y=T2;
    for(i=0; i<m; i++) ct[i]=0;
    for(i=0; i<n; i++) ct[x[i]=st[i]]++;
    for(i=1; i<m; i++) ct[i]+=ct[i-1];
    for(i=n-1; i>=0; i--)
        sa[--ct[x[i]]]=i;
    for(k=1,p=1; p<n; k<<=1,m=p)
    {
        for(p=0,i=n-k; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=k) y[p++]=sa[i]-k;
        for(i=0; i<m; i++) ct[i]=0;
        for(i=0; i<n; i++) ct[x[y[i]]]++;
        for(i=1; i<m; i++) ct[i]+=ct[i-1];
        for(i=n-1; i>=0; i--) sa[--ct[x[y[i]]]]=y[i];
        for(swap(x,y),p=1,x[sa[0]]=0,i=1; i<n; i++)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
    }
}
void gethe(char *st)
{
    int i,j,k=0;
    for(i=0;i<n;i++) rk[sa[i]]=i;
    for(i=0;i<n-1;i++)
    {
        if(k) k--;
        j=sa[rk[i]-1];
        while(st[i+k]==st[j+k]) k++;
        he[rk[i]]=k;
    }
}
int main()
{
    int i,j,l,p,tp,low,hi,id,pl,tt,a,b,cas=1;
    prermq();
    while(scanf("%s",txt),txt[0]!='#')
    {
        n=strlen(txt);
        n++;
        m=150;
        getsa(txt);
        gethe(txt);
        rmq_init();
        ans=1,id=ptr=0,pl=1;
        for(l=1;l<n;l++)
        {
            for(p=l;p<n;p+=l)
            {
                low=min(rk[p-l],rk[p]);
                hi=max(rk[p-l],rk[p]);
                tt=rmq_min(low+1,hi);
                tp=tt/l+1;
                if(tp>ans)
                    ans=tp,ptr=0,alen[ptr++]=l;
                else if(tp==ans&&alen[ptr-1]!=l)
                    alen[ptr++]=l;
                if(tt%l)
                {
                    a=p-l-(l-tt%l);
                    b=p-(l-tt%l);
                    if(a>=0)
                    {
                        low=min(rk[a],rk[b]);
                        hi=max(rk[a],rk[b]);
                        tt=rmq_min(low+1,hi);
                        tp=tt/l+1;
                        if(tp>ans)
                            ans=tp,ptr=0,alen[ptr++]=l;
                        else if(tp==ans&&alen[ptr-1]!=l)
                            alen[ptr++]=l;
                    }
                }
            }
        }
        for(i=1,pl=-1;i<n;i++)//枚举sa
        {
            for(j=0;j<ptr;j++)
            {
                tp=sa[i]+alen[j];
                if(tp>=n)
                    continue;
                tp=rk[tp];
                a=min(i,tp);
                b=max(i,tp);
                if(rmq_min(a+1,b)>=(ans-1)*alen[j])
                {
                    pl=alen[j];
                    id=min(sa[a],sa[b]);
                    break;
                }
            }
            if(pl!=-1)
                break;
        }
        pl=ans*pl;
        for(i=0;i<pl;i++)
            atx[i]=txt[id+i];
        atx[pl]=0;
        printf("Case %d: %s\n",cas++,atx);
    }
    return 0;
}
/*
dabcabcabce
baccdbaccdbacbdbacbd
*/