AC code:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=100100;

int n,Tnum;
int f[maxn][18],g[maxn][18],h[maxn][18],s[maxn],Log[maxn];
int sa1[maxn],rank1[maxn],ht1[maxn],sa2[maxn],rank2[maxn],ht2[maxn],cnt[maxn];
char st[maxn];

void init()
{
     memset(rank1,0,sizeof(rank1));
     memset(rank2,0,sizeof(rank2));
     n=strlen(st+1); Tnum=0;
     for(int i=1;i<=n;i++) s[i]=st[i],Tnum=max(Tnum,s[i]);
     s[n+1]=-1;//****
}

void build(int *sa,int *x,int *y,int m)
{
     int i,j=0;
     for(i=1;i<=m;i++) cnt[i]=0;
     for(i=1;i<=n;i++) cnt[x[i]=s[i]]++;
     for(i=1;i<=m;i++) cnt[i]+=cnt[i-1];
     for(i=1;i<=n;i++) sa[cnt[x[i]]--]=i;
     for(int k=1;k<n;k<<=1,j=0)
     {
         for(i=n-k+1;i<=n;i++) y[++j]=i;
         for(i=1;i<=n;i++) if(sa[i]>k) y[++j]=sa[i]-k;
         for(i=1;i<=m;i++) cnt[i]=0;
         for(i=1;i<=n;i++) cnt[x[i]]++;
         for(i=1;i<=m;i++) cnt[i]+=cnt[i-1];
         for(i=n;i>=1;i--) sa[cnt[x[y[i]]]--]=y[i];
         swap(x,y); m=0;
         for(i=1;i<=n;i++)
             if(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=m; else x[sa[i]]=++m;
         if(m==n) break;
     }
}

void getheight(int *sa,int *rank,int *ht)
{
     for(int i=1;i<=n;i++) rank[sa[i]]=i;
     for(int i=1,j=0;i<=n;i++)
     {
         if(j) j--;
         int k=sa[rank[i]-1];
         while(s[k+j]==s[i+j]) j++;
         ht[rank[i]]=j;
     }
}

int lcp(int (*x)[18],int l,int r)
{
    if(l>r) swap(l,r); l++;
    int k=Log[r-l+1];
    return min(x[l][k],x[r-(1<<k)+1][k]);
}

int getmin(int l,int r)
{
    int k=Log[r-l+1],x=r-(1<<k)+1;
    if(rank1[h[l][k]]<rank1[h[x][k]]) return h[l][k]; else return h[x][k];
}

void RMQ1(int (*x)[18],int *y)
{
     int k=Log[n];
     for(int i=1;i<=n;i++) x[i][0]=y[i];
     for(int j=1;j<=k;j++)
         for(int i=1;i<=n-(1<<j)+1;i++) x[i][j]=min(x[i][j-1],x[i+(1<<(j-1))][j-1]);
}

void RMQ2()
{
     int k=Log[n];
     for(int i=1;i<=n;i++) h[i][0]=i;
     for(int j=1;j<=k;j++)
         for(int i=1;i<=n-(1<<j)+1;i++)
         {
             int x=i+(1<<(j-1));
             if(rank1[h[i][j-1]]>rank1[h[x][j-1]]) h[i][j]=h[x][j-1]; else h[i][j]=h[i][j-1];
         }
}

void predeal()
{
     build(sa1,rank1,ht1,Tnum); getheight(sa1,rank1,ht1);
     for(int i=1;i<=n;i++) s[i]=st[n-i+1];
     build(sa2,rank2,ht2,Tnum); getheight(sa2,rank2,ht2);
     RMQ1(f,ht1); RMQ1(g,ht2); RMQ2();
}

void work()
{
     predeal();
     int p=0,c=0,len=0,m,k,l,r,x,y,N=n/2;
     for(int i=1;i<=N;i++)
     {
         m=i>1?n/i-1:n/i;
         if(m<c) break;
         for(int j=1;j<=m;j++)
         {
             y=i*j; k=lcp(f,rank1[y],rank1[y+i]);
             l=y-lcp(g,rank2[n-y-i+1],rank2[n-y+1])+1; r=y-(i-k%i);
             if(l>r) r=y; if(l>y) l=y; y=getmin(l,r);
             k=lcp(f,rank1[y],rank1[y+i]); x=k/i+1;
             if(x>c || (x==c && rank1[y]<rank1[p])) c=x,p=y,len=c*i;
         }
     }
     for(int i=0;i<len;i++) printf("%c",st[p+i]);
     printf("\n");
}

int Log2(int x)
{
    int len=0;
    for(;x;x>>=1) len++;
    return len-1;
}

int main()
{
    int TT=0,N=maxn-5;
    for(int i=1;i<=N;i++) Log[i]=Log2(i);
    while(scanf(" %s",st+1)!=EOF)
    {
          if(st[1]=='#') break;
          printf("Case %d: ",(++TT));
          init();
          work();
    }
    return 0;
}

• Re:终于过了，两个后缀数组，三个RMQ，O(nlogn) (35) wshjz 2016-08-01 18:14:48