1 #include
     
       2 #include
      
        3 typedef long long LL; 4 #define MAXN 50010 5 char s[MAXN]; 6 int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN]; 7 int sa[MAXN],height[MAXN],Rank[MAXN]; 8 inline bool cmp(int *r,int a,int b,int len) 9 {10     return r[a]==r[b]&&r[a+len]==r[b+len];11 }12 void SA(int n,int m)13 {14     int i,j,p,*x=wa,*y=wb,*t;15     for(i=0;i
       
        =0;i--)22         sa[--ws[x[i]]]=i;23     for(j=p=1;p
        
         <<=1,m=p)24     {25         for(p=0,i=n-j;i
         
          =j)30                 y[p++]=sa[i]-j;31         }32         for(i=0;i
          
           =0;i--)39 sa[--ws[wv[i]]]=y[i];40 for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i