基础（据说）：基数排序：https://blog.csdn.net/zhen921/article/details/80354096

模板题：https://www.luogu.org/problem/P3809

学习粗：https://www.cnblogs.com/chenxiaoran666/p/SuffixSort.html

　　　　https://www.cnblogs.com/victorique/p/8480093.html#autoid-1-2-1

#include
      
       using namespace std; const int N=1e6+6;int n,SA[N+5],rk[N+5],pos[N+5],tot[N+5];inline void RadixSort(int S)//基数排序，S表示字符集大小{    int i;    for(i=0;i<=S;++i) tot[i]=0;//清空数组    for(i=1;i<=n;++i) ++tot[rk[i]];//从1到n枚举，将tot[rk[i]]加1    for(i=1;i<=S;++i) tot[i]+=tot[i-1];//累加    for(i=n;i;--i) SA[tot[rk[pos[i]]]--]=pos[i];//倒序枚举，更新SA数组}inline void Solve(char *s){    int i,k,cnt=0,Size=122;//初始化字符集大小为122（即'z'的ASCII码）    for(n=strlen(s),i=1;i<=n;++i) rk[pos[i]=i]=s[i-1];//初始化rk数组和pos数组    for(RadixSort(Size),k=1;cnt
       
        <<=1)//先是一遍基数排序，然后倍增枚举k，直至所有后缀各不相同    {        for(Size=cnt,cnt=0,i=1;i<=k;++i)             pos[++cnt]=n-k+i;//将长度小于等于k的后缀先加入数组中，此时的cnt相当于计数器        for(i=1;i<=n;++i)             SA[i]>k&&(pos[++cnt]=SA[i]-k);//对于排名大于k的字符串，将其加入数组中        for(RadixSort(Size),i=1;i<=n;++i)             pos[i]=rk[i];//基数排序一遍，然后将rk数组的值全部赋值给pos数组        for(rk[SA[1]]=cnt=1,i=2;i<=n;++i)             rk[SA[i]]=(pos[SA[i-1]]^pos[SA[i]]||pos[SA[i-1]+k]^pos[SA[i]+k])?++cnt:cnt;//利用SA数组来得到rk，此时的cnt存储不同的字符串个数，从而得到排名    }    for(i=1;i<=n;++i)         printf("%d ",SA[i]);}char s[N];int main(){    scanf("%s",s);    Solve(s);    return 0;}