找了半天终于找到一个可以提交的地方。。。

 

题解：

任何一个重复子串，都必然是某两个后缀的最长公共前缀。

因为，两个后缀的公共前缀，它出现在这两个后缀中，并且起始位置时不同的，所以这个公共前缀必然重复出现两次以上（可重叠）。

而任何两个后缀的最长公共前缀为某一段height值中的最小值，所以最大为height值中的最大值（即某个lcp(sa[i],sa[i+1]））。

所以只要算出height数组，然后输出最大值就可以了。

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 #define N 50050 8  9 using namespace std;10 11 int wa[N],wb[N],wc[N],wv[N];12 int r[N],sa[N];13 char str[N];14 int rank[N],height[N];15 16 inline bool cmp(int *r,int a,int b,int l)17 {18     return r[a]==r[b]&&r[a+l]==r[b+l];19 }20 21 inline void da(int *r,int *sa,int n,int m)22 {23     int i,j,p,*x=wa,*y=wb,*t;24     for(i=0;i
           
            =0;i--) sa[--wc[x[i]]]=i;28 for(j=1,p=1;p
            
             <<=1,m=p)29 {30 for(i=n-j,p=0;i
             
              =j) y[p++]=sa[i]-j;32 for(i=0;i
              
               =0;i--) sa[--wc[wv[i]]]=y[i];37 for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i
               
                ans) ans=height[i],pos=sa[i];62 for(int i=pos;i