第一道后缀数组，求出最大的height值即可。更多的是当个模板用吧。

code:

#include<cstdio>

//

最长重复子串

#include<cstring>

const 

int maxn = 

10001 ;

int wa[maxn], wb[maxn], wv[maxn], ws[maxn], rank[maxn], height[maxn], sa[maxn], s[maxn] ;

char str[maxn] ;

int cmp(

int *r,

int a,

int b,

int l){

    

return r[a]==r[b] && r[a+l]==r[b+l] ;

}

void da(

int *r, 

int *sa, 

int n, 

int m){

    

int i, j, p, *x = wa, *y = wb, *t ;

    

for(i=

0; i<m; i++) ws[i] = 

0 ;

    

for(i=

0; i<n; i++) ws[x[i]=r[i]] ++ ;

    

for(i=

1; i<m; i++) ws[i] += ws[i-

1] ;

    

for(i=n-

1; i>=

0; i--) sa[--ws[x[i]]] = i ;

    

for(j=

1,p=

1; p<n; j*=

2, m=p){

        

for(p=

0,i=n-j; i<n; i++) y[p++] = i ;

        

for(i=

0; i<n; i++) 

if(sa[i]>=j) y[p++] = sa[i] - j ;

        

for(i=

0; i<n; i++) wv[i] = x[y[i]] ;

        

for(i=

0; i<m; i++) ws[i] = 

0 ;

        

for(i=

0; i<n; i++) ws[wv[i]] ++ ;

        

for(i=

1; i<m; i++) ws[i] += ws[i-

1] ;

        

for(i=n-

1; i>=

0; i--) sa[--ws[wv[i]]] = y[i] ;

        

for(t=x, x=y, y=t, p=

1, x[sa[

0]]=

0, i=

1; i<n; i++)

        x[sa[i]] = cmp(y, sa[i-

1], sa[i], j) ? p - 

1 : p ++ ;

    }

    

return ;

}

void calheight(

int *r,

int *sa,

int n){

    

int i, j, k = 

0 ;

    

for(i=

1; i<=n; i++) rank[sa[i]] = i ;

//

获取rank值 O(n)

    

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++) ;

    

return ;

}

int main(){

    

int t, n, i, j, max ;

    scanf(

"

%d

", &t) ;

    

while(t--){

        scanf(

"

%s

", str) ;

        n = strlen(str) ;

        

for(i=

0; i<n; i++)

            s[i] = (

int)str[i] ;

        s[n] = 

0 ;

        da(s, sa, n+

1, 

255) ;

        calheight(s, sa, n) ;

        max = 

0 ;

        

for(i=

1; i<=n; i++)

            

if(max<height[i])

                max = height[i], j = sa[i] ;

        

for(i=j; i-j<max; i++)

            printf(

"

%c

", str[i]) ;

        printf(

"

\n

") ;

    }

    

return 

0 ;}