前言：
紫书代码如果输入的字符串是就会错，需要把;改成，同时的板子也要改一个地方，最后的索引范围为。
我太难了，之前看了好久才懂的模板，现在又看不懂了，看了好久第二个模板还是懵逼。。
1.用sort()函数求后缀数组sa[]
总复杂度：O()

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;                    //字符串的长度
char s[MAXN];                            //输入字符串
int sa[MAXN],rk[MAXN],tmp[MAXN+1],height[MAXN];
int n,k;

/*比较函数
每一步使得 sa[]从0到n-1对应的字符串（从sa[i]开始的字串）按照组合数大小从小到大排序
最后一步使得sa[]从0到n-1对应的字符串（从sa[i]开始的字串）按照字典序从小到大排列*/
bool comp_sa(int i,int j){                //组合数有两个部分，高位是rk[i],低位是rk[i+k]
    if(rk[i]!=rk[j])                    //先比较高位：rk[i]和rk[j]
        return rk[i]<rk[j];
    else{                                //高位相等，再比较低位的rk[i+k]和rk[j+k]
        int ri = i+k<=n? rk[i+k] : -1;
        int rj = j+k<=n? rk[j+k] : -1;
        return ri<rj;
    }
}
void build_sa(int n){                            //计算字符串s的后缀数组
    for(int i=0;i<=n;i++){
        rk[i]=s[i];                        //字符串的原始数值
        sa[i]=i;                        //后缀数组，在每一步记录当前排序后的结果
    }
    for(k=1;k<=n;k*=2){                    //开始一步步操作，每一步递增两倍进行组合
        sort(sa,sa+n,comp_sa);       //排序，结果记录在sa[]中(根据rk[]值的大小（各个字串的大小）从小到大将rk[]的下标
                                    //（从第几个字符开始的）存在sa[]中)
                                    //r[i]和i是固定的 
        tmp[sa[0]]=0;                    //rk[sa[i]]=i;
        for(int i=0;i<n;i++)            //用sa[]倒推组合数，并记录在tmp[]中，用于临时存放rk[]的新值
            tmp[sa[i+1]]= tmp[sa[i]] + (comp_sa(sa[i],sa[i+1])?1:0);//因为sa[]存的是0~n-1的数，而此时的rk[]有重复 
                                        //的数字，所以如果当前排名i+1的后缀和i的后缀相等就取tmp[sa[i]]
                                        //反之取 tmp[sa[i]]+1 
        for(int i=0;i<n;i++)            //把tmp[]复制给rk[]，用于下一步操作
            rk[i] = tmp[i];                //每一步改变最高位 ，最后一步得到每个字串的排名
    }
}
int main(){
    while(scanf("%s",s)!=EOF){
        n=strlen(s);
        build_sa(n+1);                        //求后缀数组
        for(int i=1;i<=n;i++)
            printf("%d ",sa[i]);        //打印后缀数组
        puts("");
    }
    return 0;
}

2.用基数排序求后缀数组sa[]
n个数，每个数有d位，每一位有k种可能
基数排序的复杂度是O(d(n+k)) 存储空间是O(n+k);
当d比较小的情况下，是比快速排序更好的办法；
总复杂度：O(nlog二n)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;                    //字符串的长度
char s[MAXN];                            //输入字符串
int sa[MAXN],cnt[MAXN],t1[MAXN],t2[MAXN],rk[MAXN],height[MAXN];
int n;

void build_sa(int n) {                                //n是字符串长度
    int m=127;                               
    //m是小写字母的ASCII码值范围，构成字符串s的后缀数组，每个字符的值必须为0~m-1
    int i,*x=t1,*y=t2;
    for(i=0;i<m;i++)    cnt[i]=0;
    for(i=0;i<n;i++)    cnt[x[i]=s[i]]++;//记录每个字符出现的次数 
    for(i=1;i<m;i++)    cnt[i]+=cnt[i-1];
    //记录ASCII码小于等于i的字符个数 ，也就是每个字符的排名 
    for(i=n-1;i>=0;i--)  sa[--cnt[x[i]]]=i;
    //--cnt[x[i]]就是一个字符出现多次，最后一个出现的排名最高
    //sa[]:从0到n-1
    for(int k=1;k<=n;k*=2){                    //利用对长度为k的排序结果对长度为2k的排序
        int p=0;
        //2nd
        for(i=n-k;i<n;i++)    y[p++]=i;
        for(i=0;i<n;i++)    if(sa[i]>=k)    y[p++]=sa[i]-k;
        //1st
        for(i=0;i<m;i++)    cnt[i]=0;
        for(i=0;i<n;i++)    cnt[x[y[i]]]++;
        for(i=1;i<m;i++)    cnt[i]+=cnt[i-1];
        for(i=n-1;i>=0;i--) sa[--cnt[x[y[i]]]]=y[i];
        swap(x,y);//y为中间数组更新x 
        p=1; x[sa[0]]=0;
        for(i=1;i<n;i++)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
            //得到中间的rk[]值 
        if(p>=n)    break;
        m=p;
    }
}
int main(){
    while(scanf("%s",s)!=EOF){
        n=strlen(s);
        build_sa(n+1);                        //求后缀数组
        for(int i=1;i<=n;i++)
            printf("%d ",sa[i]);        //打印后缀数组
        puts("");
    }
    return 0;
}

3.高度数组height[]
和最长公共前缀(LCP)有关

void getheight(){                        //n是字符串长度
    int i,j,k=0;
    for(i=0;i<=n;i++)    rk[sa[i]]=i;    //用sa[]推导rk[]
    for(i=0;i<n;i++){
        if(k)    k--;
        int j=sa[rk[i]-1];
        while(s[i+k]==s[j+k])    k++;
        height[rk[i]]=k;
    }
}