const int MAXN = 200000;

int sa[MAXN]; //排第几的是哪个后缀  
//sa[1~n]为有效值，sa[0]必定为n是无效值  
int rank[MAXN]; //rank后缀i排第几  
//rk[0~n-1]为有效值，rk[n]必定为0无效值  
int height[MAXN]; //sa[i]和sa[i-1]的最长公共前缀  
//ht[2~n]为有效值  
int t1[MAXN],t2[MAXN],c[MAXN]; //临时数组空间

void build_sa(int s[],int n,int m) 
//s为要处理的字符串的转化形式,将所有字符转化成1---m的范围的int
//n为长度,s[n]必须为0,m为字符集大小
{  
    n++;
    int *x=t1,*y=t2;  
    //第一轮基数排序  
    for(int i=0;i<m;i++) c[i]=0;  
    for(int i=0;i<n;i++) c[x[i]=s[i]]++;  
    for(int i=1;i<m;i++) c[i]+=c[i-1];  
    for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;  
    for(int j=1;j<=n;j<<=1)  
    {  
        int p=0;  
        //直接利用sa数组排序第二关键字  
        for(int i=n-j;i<n;i++) y[p++]=i;  
        for(int i=0;i<n;i++)  
            if(sa[i]>=j) y[p++]=sa[i]-j;  
        //基数排序第一关键字  
        for(int i=0;i<m;i++) c[i]=0;  
        for(int i=0;i<n;i++) c[x[y[i]]]++;  
        for(int i=1;i<m;i++) c[i]+=c[i-1];  
        for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];  
        //根据sa和x数组计算新的x数组  
        swap(x,y);  
        p=1,x[sa[0]]=0;  
        for(int i=1;i<n;i++)  
            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;  
        if(p>=n) break;  
        m=p;  
    }  
}  

void getheight(int s[],int n)  
{  
    int k=0;  
    for(int i=0;i<=n;i++)  
        rank[sa[i]]=i;  
    for(int i=0;i<n;i++)  
    {  
        if(k) k--;  
        int j=sa[rank[i]-1];  
        while(s[i+k]==s[j+k]) k++;  
        height[rank[i]]=k;  
    }  
}