比较直观的思路是用sort直接排序，但是字符串的比较是o(n)的，所以导致总的时间复杂度是n^2logn
显然是不然通过的，所以需要在比较字符串的时候做一些优化
字符串hash优化：
用字符串hash可以在o(1)的时间比较两个字符串是否相同(但还是无法确定大小)
观察发现：在字符串比较时，一般从头往后遍历，找到第一个字符不相等时便可以比较出结果
那么，我们可以采用二分前缀的方法在o(logn)的时间内找出两个字符串的公共前缀，然后比较后面一个字符。
总的时间复杂度为o(nlog^2n)

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std ;

typedef unsigned long long ULL ;
const int MAX = 300010, base = 131;
char str[MAX] ; // 原字符串
ULL h[MAX], p[MAX] = {1} ; 
int sa[MAX], n; 

ULL getHash(int l, int r){ // 获得区间[l, r]的字符串hash
    return h[r] - h[l - 1] * p[r - l + 1] ; 
}

int getMaxCommonPrefix(int a, int b){
    int l = 0, r = min(n - a + 1, n - b + 1) ;
    while( l < r ){ // 二分最长公共前缀
        int mid = l + r + 1 >> 1 ;
        if( getHash(a, a + mid - 1) == getHash(b, b + mid - 1)){
            l = mid ;
        } else{
            r = mid - 1 ;
        }
    }
    return l ;
}

bool cmp(int a, int b){
    int l = getMaxCommonPrefix(a, b) ;
    return str[a + l] < str[b + l] ;
}

int main(){
    scanf("%s", str + 1) ;
    n = strlen(str + 1) ;
    for(int i = 1; i <= n; i++){
        h[i] = h[i - 1] * base + str[i] - 'a' + 1;
        p[i] = p[i - 1] * base ;
        sa[i] = i ;
    }
    sort(sa + 1, sa + n + 1, cmp) ;
    for(int i = 1; i <= n; i++){
        printf("%d ", sa[i] - 1) ;
    }
    printf("\n0") ;
    for(int i = 2; i <= n; i++){
        printf(" %d", getMaxCommonPrefix(sa[i], sa[i-1])) ;
    }
    return 0 ;
}

提交发现是可以通过的，但是时间开销有点，所以还可以进一步优化

da算法()：
在采取字符串hash比较里，忽略掉了一个关键点：我们需要进行排序的是同一个字符串的不同后缀
这些后缀有什么特征呢？我们先看下列数据
如原字符串 str = “babbc” , 那么它所有后缀为
①: babbc
②: abbc
③: bbc
④: bc
⑤: c
观察发现，第i个后缀字符串的第二个字符便是第i + 1个后缀字符串的首字符
这有什么用呢？熟悉基数排序的小伙伴便能发现了：
我们对这些后缀的首字母进行排序
然后就可以利用首字母排序后的结果直接确定每个第二个字母排序的结果
(因为第i个后缀字符串的第二个字符排序结果就是第i+1个字符的首字母的排序结果)
但是第n(n为字符串长度)后缀字符串是没有第二个字符的，换句话说他的第二个字符是空字符
而在比较的过程中空字符是最小的，所以在比较第二字符时需要将它的排名设置为第一
重点来了，确定了第二字符的排名并再次进行基数排序后，我们就可以知道这些后缀中前两个字符的排序顺序
那么，是不是可以直接确定第三、第四字符的排名呢？
显然是可以的，因为第i个后缀字符串的第三、第四字符就是第i-2个后缀字符串的第一、第二个字符
以此类推，在前i个字符已经排好序的情况下，我们可以确定第i到第2i个字符的排名(这个排名称之为第二关键字)
然后用第二关键字更新前2i个字符的排名(采用基数排序(o(n))
因此，可以采用倍增的思想在o(logn)的时间来完成此过程，因为每步过程中基数排序的时间是o(n)的
所有总的时间复杂度为o(nlogn)
重要变量说明(很重要):
sa : 排名为i对应的下标，如 s[i] = j 表明排名为i的字符串是第j个后缀字符串(即下标为j)
rak: 下标为i对应的排名，如 s[i] = j 表明第i个后缀字符串排名为j(与sa相反，在排序的过程中需要使用到它)
tp : 第二关键字对应的下标，如 tp[i] = j 表明第二关键字排名为i的字符串是第j个字符串
height: height[i] 为 sa[i] 和 sa[i-1] 的公共前缀
h: h[i] = height[rak[i]], 即第i个后缀字符串与他前一名的后缀字符串的公共前缀(利用h[i]可以在o(n)的时间内求出height(n))

上代码！

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std ;

const int MAX = 300010 ;
char str[MAX] ; // 原字符串
int N, M ; // N：字符串长度， M 基数排序中桶的大小
int sa[MAX], rak[MAX], tp[MAX], tak[MAX], height[MAX], h[MAX] ; // tak: 计数器(基数排序的过程中会使用)

void Qsort(){ // 基数排序
    for(int i = 0; i <= M; i++){ // 计数器归零
        tak[i] = 0 ;
    }
    for(int i = 1; i <= N; i++){ // 统计排名
        tak[rak[i]]++ ;
    }
    for(int i = 1; i <= M; i++){ // 求前缀和(这三步没看懂的建议先学会基数排序)
        tak[i] += tak[i-1] ;
    }
    for(int i = N; i >= 1; i--){ // 降序，第二关键字排名后面的优先确定排名
        // 这步很精妙。首先，tp[i]取出排名为i的下标，rak[tp[i]]则取出这个下标在tak中对应的下标
        // tak[rak[tp[i]]]便得到这个下标的排名了(取了后排名需要减一)
        sa[tak[rak[tp[i]]]--] = tp[i] ;
    }
}

void Suffixsort(){ 
    M = 'z' - 'a' + 1 ; // 初始化桶的大小(不小于rak中的最大值)
    for( int i = 1; i <= N; i++){
        rak[i] = str[i] - 'a' + 1 ; // 先用每个后缀首字母的ASCII相对值作为初始轮排名
        tp[i] = i ; // 这里仅用于记录位置
    }
    Qsort() ; // 初始轮排序后便知道了sa的顺序(即首字母的相等顺序)

    // p：有效排名  解释：若第i个后缀字符串和第j个后缀字符串的前k(k为当前比较的字符数量)个字符都相等
    // 则认为第i个和第j个后缀字符串的比较是无效的，将他们设置为相同的排名。当p=N时所有的排名都有效，排序结束
    for(int w = 1, p; p < N; M = p, w <<= 1){ // w：倍增长度(也可以理解为当前排好序的字符数量)  
        p = 0 ; // 注意：这里的p仅用于排名计数
        for(int i = 1; i <= w; i++){ 
            // 因为有w个后缀字符串第二关键关键字为空字符，所有将他们的排名设置为前列
            tp[++p] = N - w + i ;
            // 因为这里将前w个排名占据了，所有后面的排名需要往后推(这也是用p将排名计数的原因)
        }
        for( int i = 1; i <= N; i++){ // 根据sa(已排好序的字符)更新tp(第二关键字)
            // 这里有点抽象
            if( sa[i] > w ){ // 首先 sa[i] > w 是筛选出后N - w个后缀字符串
                // sa[i] - w 是将找到第sa[i]后缀字符串的第前w个后缀字符串prev
                // 即第prev个后缀字符串的第后w个后缀字符串是sa[i]
                tp[++p] = sa[i] - w ; 
                // 这行代码的意思是将排名为p(原本是i，往后推了)的下标设置为第sa[i]-w的下标
            }
        }
        Qsort() ; // 用得到的第二关键字对排名进行更新
        //更新后tp暂时没用了，但需要利用原rak对rak进行更新，所以这里用tp暂存原rak
        memcpy(tp, rak, sizeof(tp)) ;
        rak[sa[1]] = p = 1 ; // 这里的p就是有效排名了
        for(int i = 2; i <= N; i++){
            // 如果当前排名与前一个排名的第一和第二关键字都相同(即排名相同)，则有效排名不增加(还未比较出结果)  
            p += (tp[sa[i]] != tp[sa[i-1]] || tp[sa[i] + w] != tp[sa[i-1] + w]) ;
            rak[sa[i]] = p ;
        }
    }
}

void get_height(){
    // 这里有个很重要的定理：h[i] >= h[i-1] - 1。证明过程比较复杂，略。
    for(int i = 1; i <= N; i++){
        h[i] = max(h[i-1] - 1, 0) ;
        while(str[sa[rak[i]] + h[i]] == str[sa[rak[i]-1] + h[i]]){
            h[i] ++ ;
        }
        height[rak[i]] = h[i] ;
    }
}

int main(){
    scanf("%s", str + 1) ;
    N = strlen(str + 1) ;
    Suffixsort() ;
    get_height() ;
    for(int i = 1; i <= N; i++){
        printf("%d ", sa[i] - 1) ;
    }
    puts("") ;
    for(int i = 1; i <= N; i++){
        printf("%d ", height[i]) ;
    }
}