读入一个长度为 n的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 到 n 。
摘自：
https://xminh.github.io/2018/02/27/%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84-%E6%9C%80%E8%AF%A6%E7%BB%86(maybe)%E8%AE%B2%E8%A7%A3.html
工具：
1.基数排序 2. 倍增
(此题不讨论lcp)
中心思想：
从1~n每个位置，按取的关键字个数（2^0,2^1,...,2^k倍增)来基数排序，直到排序没有重复为止。
tot//每次排序后可分成多少不同组
s[]//存原数组
cnt[]//桶计数
x[]//按第一关键字排序的下表位置
y[]//按第二关键字排序的下标位置
sa[]//记录每次排序后真正的下标位置
上代码：
int get_sa(){ For(i,1,n)cnt[x[i]=s[i]]++; For(i,2,122)cnt[i]+=cnt[i-1];//122是z的ascii码 FFor(i,n,1)sa[cnt[x[i]]--]=i; //上面一坨基数排序处理2^0 for(int k=1;k<=n;k<<=1){ int num=0; For(i,n-k+1,n)y[++num]=i;//i>=n-k+1说明下一位关键字位数不够，需要补零，既然补零那么一定最小，所以先加入队列 For(i,1,n)if(sa[i]>=k+1)y[++num]=sa[i]-k;//如果sa[i]>=k+1,说明sa[i]可以成为别人的下一位关键字，那么把它对应的那个别人加进来 me(cnt,0);//剩下的数继续走基数排序流程 For(i,1,n)cnt[x[i]]++; For(i,2,tot)cnt[i]+=cnt[i-1]; FFor(i,n,1)sa[cnt[x[y[i]]]--]=y[i],y[i]=0; swap(x,y);//因为要x的数组内容当做下一轮循环的第一关键字，且接下来更新时需要用到旧数组，所以用y顶替下 x[sa[1]]=1; num=1; For(i,2,n)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num);//第一第二关键字合并起来后再排序 if(num==n)break; tot=num; } For(i,1,n)cout<<sa[i]<<" "; }