1 #include
     
        2 #include
      
         3 #include
       
          4 using namespace std;  5 #define MAXN 100010  6 #define MAXM 20  7 char s[MAXN];  8 int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN];  9 int sa[MAXN],height[MAXN],rk[MAXN]; 10 int st[MAXM][MAXN],log2[MAXN]; 11 inline bool cmp(int *r,int a,int b,int L) 12 { 13     return r[a]==r[b]&&r[a+L]==r[b+L]; 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
            
             =(1<
             
              j) 82 swap(i,j); 83 i++; 84 int k=log2[j-i+1]; 85 return min(st[k][i],st[k][j-(1<
              
               n) 93 break; 94 t=LCP(sa[i],sa[i+k-1]); 95 if(t>height[i]&&(i+k>n||i+k<=n&&t>height[i+k])) 96 { 97 for(j=sa[i];j