读入一个长度为 \(n\) 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 \(1\) 到 \(n\)
输入样例:
ababa
输出样例:
5 3 1 4 2
样例解释:
后缀：与前缀类似，如上述字符串后缀分别为 \(ababa\),\(baba\),\(aba\),\(ba\),\(a\)
字符串排序：对于两个字符串，同时从第一位比较到最后一位（不足补0），位数大的不一定大
实例1：\(baaaa>aaaaa\)（第一位\(b\)>\(a\)）
实例2：\(b>abbbbbbbbb……\)（第一位\(b\)>\(a\)）
实例3：\(abd>abcde\)（第三位\(d\)>\(c\)）
实例4：\(abcd>abc\)（第四位\(d\)>空）
因此样例中\(a\)<\(aba\)<\(ababa\)<\(ba\)<\(baba\)
数据范围:
\(n≤10^6\)
这道题当然可以暴力求解，然而这数据范围显然会让暴力炸掉
因此我们需要使用一种全新的算法——后缀数组
for(register int i=n;i>=1;i--) a[i]+=a[i+1]
不是这个啦！这个是后缀和！！！
咳咳
首先我们需要了解基数排序（Rsort）
在很多位数相同的短数字排序时，其效率优于其他排序算法（归并，快速及堆等）
其思路很简单（这里以两位数排序为例），先以个位为关键字排序，再以十位为关键字排一次序
如以下样例：
65,48,19,82,38,49,67,18,23,61
按照个位排序后如下：
61,82,23,65,67,48,38,18,19,49
再按照十位排序：
18,19,23,38,48,49,61,65,67,82
这样就排序完成了
同理，我们将串中的字符换为数字，几位合并后作为关键字排序即可
高清无码注释版代码见下：
#include<bits/stdc++.h> #define fo(i,j,k) for(register int i=1j;i<=k;++i) #define N 1000005 using namespace std; char s[N]; int a[N],rk[N],sa[N],tp[N],tax[N],n,m; //a暂存，rk第一关键字第i位的排名，sa排名为i的位置 //tp作为第二关键字，tax作为桶 inline void Rsort() { for(register int i=0;i<=m;++i) tax[i]=0;//清零桶的数据 for(register int i=1;i<=n;++i) ++tax[rk[tp[i]]];//出现的第一关键字+1 for(register int i=1;i<=m;++i) tax[i]+=tax[i-1];//tax中i代表这个数最多能排到第几位 for(register int i=n;i>=1;--i) sa[tax[rk[tp[i]]]--]=tp[i]; //处理这一轮的SA，（第一关键字相同时，第二关键字越大排名越靠后） } inline void Suffix() { for(register int i=1;i<=n;++i) rk[i]=a[i],tp[i]=i; //第一轮直接使用ascii码和位置当关键字 Rsort(); for(register int k=1;k<=n;k<<=1) { int num=0; for(register int i=n-k+1;i<=n;++i) tp[++num]=i; //从n-k+1到n，第二关键字都为零，所以存入数组 for(register int i=1;i<=n;++i) if(sa[i]>k) tp[++num]=sa[i]-k; //sa有序，当sa[i]大于k时，sa[i]会作为其他的第二关键字，所以sa[i]-k进队 Rsort(); swap(rk,tp);//用tp存下一轮的rk rk[sa[1]]=1; num=1; for(register int i=2;i<=n;++i) rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?num:++num; //比较第一关键字和第二关键字是否相同，相同就是num,否则是num+1 if(num==n) break;//当有n种排名时，结束 m=num;//tp种类 } return; } int main() { gets(s); n=strlen(s);//字符串长度 m=122;//字符个数 for(register int i=0;i<n;++i) a[i+1]=s[i]; Suffix(); for(register int i=1;i<=n;++i) printf("%d ",sa[i]); return 0; }很巧妙的算法，然而因为所有数组都是一维的，使用时必须嵌套，第一遍看可能会很懵
不过没关系，对着代码多看几遍，你就可以……背到了……逃