//poj2774

#include <iostream>
using namespace std;

const int Max = 200010;
char str[Max];
int height[Max],mem[4][Max];
int *s1,*s2,*R,*B,len;

void Initial()
{
    memset(mem,0,sizeof(mem));
    s1=mem[0];
    s2=mem[1];
    R=mem[2];
    B=mem[3];    
    len = strlen(str);
    str[len++]='a'-1;

}

void CreateSuffixArray()
{
    int i,h,h2,*T;
    
    Initial();
    
    for(i=0;i<256;++i) B[i]=0;
    for(i=0;i<len;++i) B[str[i]]++;
    for(i=1;i<256;++i) B[i]+=B[i-1];

    for(i=0;i<len;++i) s1[ --B[str[i]] ] = i;
    
    for(R[s1[0]]=0,i=1; i<len; ++i){
        if(str[ s1[i] ] == str[ s1[i-1] ]) R[ s1[i] ] = R[ s1[i-1] ];
        else R[ s1[i] ] = R[ s1[i-1] ] + 1;
    }
    
    //printf("log(n) loops:\n");
    
    for(h=1; h<len && R[ s1[len-1] ] < len-1; h<<=1){
        
        //printf("\nh=%d\n",h);
        //for(i=0;i<len;++i)printf("s1[%d]=%d\n",i,s1[i]);
        //system("pause");
        
        for(i=0; i<len; ++i) B[ R[s1[i]] ] = i;
        
        for(i=len-1; i>=0; i--){
            if(h <= s1[i]) s2[ B[R[s1[i]-h]]-- ] = s1[i]-h;
        }
        
        for(i=len-h, h2 = len - (h>>1); i<h2; ++i) s2[ B[R[i]] ] = i;
           
        T=s1; s1=s2; s2=T;
    
        for(B[s1[0]]=0, i=1; i<len; ++i ){
            if( R[s1[i]] != R[s1[i-1]] || R[s1[i]+h] != R[s1[i-1]+h]) B[s1[i]] = B[s1[i-1]]+1;
            else B[s1[i]] = B[s1[i-1]];
        }
        
        T=B; B=R; R=T;
    }
}

void CalculateHeight()
{
    int i,j,k;
    for(k=0,i=0; i<len; ++i){
        if(R[i]==0) height[0]=0;
        else {
            for(j=s1[R[i]-1]; str[i+k]==str[j+k]; ++k);
            height[R[i]]=k;    
            if(k>0)k--;
        }
    }    
    
}



int main()
{
    char c;
    int ans,i,d,s,k,cs=0;
    while(true){
        gets(str);
        cs++;
        if(strcmp(str,"#")==0)break;
        
        CreateSuffixArray();
        
        //for(int i=0;i<len;++i)puts( str+(s1[i]) );
        //system("pause");
        
        CalculateHeight();

        //for(i=0;i<len;++i)printf("height[%d]=%d\n",i,height[i]);
        //system("pause");
        
        d=ans=0;
        for(i=1;i<len;++i){
            int t=height[i];
            for(int j=i;j<len && t>0 && height[j]>=t;++j){
                if( s1[j] > s1[i-1] ){
                    k=s1[j]-s1[i-1];
                    if(  t/k > ans){
                        ans = t / k;
                        s = s1[i-1];
                        d = k;
                    }    
                }
                else{
                    k=s1[i-1]-s1[j];
                    if( t/k > ans){
                        ans = t / k;
                        s = s1[j];
                        d = k;
                    }    
                }
            }

        }
        
        printf("Case %d: ",cs);
        if(ans != 0){
            //printf("s=%d d=%d ct=%d\n",s,d,ans);
            d*=ans+1;
            for(i=0;i<d; i++)putchar(str[s+i]);
        }
        else{
            c=str[0];
            for(i=1;i<len-1;++i){
                if( c>str[i] )c=str[i];
            }
            putchar(c);
        }
        putchar('\n');
    }
    
    //system("pause");
    return 0;    
}

• Re:数据弱，这算法有问题，给组数据X掉 (28) cmonkey 2012-10-19 17:18:05
  • Re:、感谢 (34) 120106701 2017-04-26 10:38:47