倍增算法，时间复杂度O(nlogn)

sa从小到大保存相对大小的下标

理解LSD，x数组，sa数组

char s[maxn];

int sa[maxn],t[maxn],t2[maxn],c[maxn],n;

void build_sa(int m)

{

    //LSD基数排序

    int *x=t,*y=t2;//x数组保存rank

    //字串长度为1，即对每一个元素的大小排序

    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;//sa从小到大保存每一个元素的下标

    for(int k=1;k<=n;k<<=1){//k为要排序的子串长

        //排序第二keyword

        int p=0;               //y[]从小到大保存第二keyword的下标

        for(int i=n-k;i<n;++i) y[p++]=i;//从第n-k位開始的字串，第二keyword为0

        for(int i=0;i<n;++i) if(sa[i]>=k) y[p++]=sa[i]-k;

                                //仅仅有下标大于k的第sa[i]个字符串的rank才干作为下一行的第sa[i]-k个字符串的第二keyword

        //排序第一keyword

                //x[y[i]]是引用第一keyword，依据LSD第二次排序要在第一次的基础上

        for(int i=0;i<m;++i) c[i]=0;//计数数组清空

        for(int i=0;i<n;++i) c[x[y[i]]]++;//统计rank出现次数

        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[]从小到大保存双keyword的下标

        p=1;swap(x,y);x[sa[0]]=0;//交换x，y数组 x[]数组从0到n-1保存rank值(0到p)

        for(int i=1;i<n;++i){

            x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k] ? p-1:p++;//注意p-1

            //因为p是计数rank值不同的字符串的数量，因此双keyword同样的串视为一样的rank

        }

        if(p>=n) break; //p个字符串的rank值都不同 ，p>=n时说明大小确立，以后即使倍增，sa也不会改变

        m=p;//用来下次基数排序的最大值

    }

}

————————————————————————————————————--————————

————————————————————————————————————————————

void build_sa()

{

    int *x=t,*y=t2;

    for(int i=0;i<m;++i) c[i]=0;

    for(int i=0;i<n;++i) c[x[i]=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[i]]]=i;

    for(int k=1;k<=n;k<<=1){

        int p=0;

        for(int i=n-k;i<n;++i) y[p++]=i;

        for(int i=0;i<n;++i) if(sa[i]>=k) y[p++]=sa[i]-k;

        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];

        int p=0;swap(x,y);x[sa[0]]=0;

        for(int i=1;i<n;++i){

            x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k] p-1:p++;

        }

        if(p>=n) break;

        m=p;

    }

}

int m;

int cmp_suffix(char *pattern,int p)

{

    return strncmp(pattern,s+sa[p],m);

}

int find(char *p)

{

    m=strlen(p);

    if(cmp_suffix(p,0)<0) return -1;

    if(cmp_suffix(p,n-1)>0) return -1;

    int l=0,r=n-1;

    while(l<=r){

        int mid=l+(r-l)/2;

        int res=cmp_suffix(p,mid);

        if(!res) return mid;

        if(res>0) l=mid+1;

        if(res<0) r=mid-1;

    }

    return -1;

}

/*

设suffix(k)是排在suffix(i-1)前一名的后缀。则它们的最长公共前缀是h[i-1]

。那么suffix(k+1)将排在suffix(i)的前面（这里要求h[i-1]>1，假设h[i-1]≤

1，原式显然成立）而且suffix(k+1)和suffix(i)的最长公共前缀是h[i-1]-1，

所以suffix(i)和在它前一名的后缀的最长公共前缀至少是h[i-1]-1。依照h[1]

，h[2]，……，h[n]的顺序计算。并利用h数组的性质，时间复杂度能够降为O

(n)。

*/

void get_height()

{

    for(int i=0;i<n;++i) rank[sa[i]]=i;

    int k=0;

    for(int i=0;i<n;++i){

        if(k) k--;

        int j=sa[rank[i]]-1;

        while(s[j+k]==s[i+k]) k++;

        height[rank[i]]=k;

    }

}