1 #include
     
        2 #include
      
         3 #include
       
          4 using namespace std;  5 #define MAXN 2200  6 #define MAXM 12  7 char s[MAXN],t[MAXN];  8 int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN];  9 int sa[MAXN],rk[MAXN],height[MAXN]; 10 int st[MAXN][MAXM]; 11 inline bool cmp(int *r,int a,int b,int len) 12 { 13     return r[a]==r[b]&&r[a+len]==r[b+len]; 14 } 15 void SA(int n,int m) 16 { 17     int i,j,p,*x=wa,*y=wb,*t; 18     for(i=0;i
        
         =0;i--) 25         sa[--ws[x[i]]]=i; 26     for(j=p=1;p
         
          <<=1,m=p) 27     { 28         for(p=0,i=n-j;i
          
           =j) 33 y[p++]=sa[i]-j; 34 } 35 for(i=0;i
           
            =0;i--) 42 sa[--ws[wv[i]]]=y[i]; 43 for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i
            
             height[q]?q:p; 79 } 80 } 81 } 82 int RMQ(int i,int j) 83 { 84 int k; 85 if(i>j) 86 swap(i,j); 87 i++; 88 for(k=0;(1<
             
              <=j-i+1;k++); 89 k--; 90 i=st[i][k]; 91 j=st[j-(1<
              
               >1;104 for(i=ans=st=0;i
               
                ans)108 {109 ans=(j<<1)-1;110 st=i-j+1;111 }112 if(i)113 {114 j=RMQ(rk[i],rk[len-i]);115 if(j<<1>ans)116 {117 ans=j<<1;118 st=i-j;119 }120 }121 }122 for(i=st;i