后缀数组（suffix array）是省选字符串题目中非常重要的算法。
本文将简略讲述其 \(O(n\log n)\) 求法，对于时间复杂度更优秀但 not practical 的做法不作提及。
考虑一种字符串比较大小的新方式。
对于长度为 \(n\) 的字符串 \(s1,s2\)，我们考虑先比较其前 \(k\) 位，若前 \(k\) 位已经能比较出大小，则比较成功，否则再比较其后 \(n-k\) 位。
这种比较方式的正确性很显然，但我们要考虑其带给我们的启示。
我们这个比较方式实际上将一个大的问题分解为了两个相对较小的问题，这实际上是一种分治。
那么，基于这种分治思想的后缀数组便应运而生了。
其采用倍增的思路，实际上很容易理解，因为分成的两个相对较小的子问题的复杂度应相对平均，故实际上最优的 \(k\) 在 \(\frac{n}{2}\) 时取到。
那么将 \(k=\frac{n}{2}\) 带入原来的思路就会得到一种显而易见的倍增，倍增的过程即是 \(k\) 从小到大，将所有长度为 \(2^{k-1}\) 的比较完了过后再进行 \(2^k\) 的比较，而边界条件则是 \(k=0\)，此时的单字符比较显然更容易。
在两个字符串比较时，两个字符串的关系可以用简单的小于等于大于来表示，但后缀数组要解决的问题则是多个字符串的比较，此时如何表示大小关系？
显然我们可以采用排名的方式，记录每个字符串排序后在有序的字符串序列中的位置，以此作为大小关系的表示方式，特别的，当两个字符串相等时，其排名也相等。
由此，后缀排序也如两个字符串的比较一样呼之欲出。
设字符串 \(s\) 的第 \(l\) 位至第 \(r\) 位构成的子串为 \(s[l\sim r]\)。
使用后缀数组进行长度为 \(2^k\) 的所有字符串排序时，被排序的字符串为 \(s[1\sim2^k],s[2\sim2^k+1],s[3\sim2^k+2]\cdots\cdots\)。
在比较 \(s[x\sim2^k+x-1]\) 和 \(s[y\sim2^k+y-1]\) 时，由于我们已经将所有长度为 \(2^{k-1}\) 的所有字符串的排名求出来的，记 \(s[z\sim2^{k-1}+z-1]\) 对应的排名为 \(rk_z\)，则这两个字符串的比较方式为：
-
先比较 \(rk_x\) 和 \(rk_y\) 的大小，若 \(rk_x\ne rk_y\) 则比较结果直接可得出。
-
若 \(rk_x=rk_y\) 则再继续比较 \(rk_{x+2^{k-1}}\) 和 \(rk_{y+2^{k-1}}\) 即可。
需要注意的是，如果两次比较后仍相同，它们的排名也需保持相同。
由此，后缀数组的过程便完成了，但如何进行字符串的排序时我们需思考的。
观察一下多个字符串比较的本质，我们发现其本质上为一个双关键字排序。
考虑朴素做法，即暴力 \(O(n\log n)\) 排序，加上倍增的 \(O(\log n)\)，总复杂度 \(O(n\log^2n)\)，在 \(10^6\) 的数据范围下通过较为吃力。
那么可以想见我们需要一种更快的排序，能够在 \(O(n)\) 的时间复杂度内完成双关键字排序。
考虑基数排序。
我们将一个包含双关键字的字符串看做一个二元组。
下面将简述过程：
\(1.\) 将所有第二关键字进行桶排序，由此得到按照第二关键字大小排列的二元组顺序。
\(2.\) 将所有第一关键字进行桶排序，并进行前缀和以获得当前排名（后面排名会不断刷新，此处的当前排名对应的是第一关键字为它且第二关键字最大的二元组）。
\(3.\) 倒序枚举根据第二关键字大小排列的二元组（倒序枚举保证了第二关键字有序），每枚举到一个二元组便将排名赋为对应桶上的排名并将该桶对应的排名 \(-1\)（倒序枚举的用处体现，对于同第一关键字的二元组，先被枚举的排名一定大于等于后被枚举的排名，因为第二关键字有序）。
由此，基数排序便完成了。
但我们发现，如此排完一次序后，所有二元组的排名将互异，但却存在两个二元组（字符串）相同的情况，怎么办？
考虑判断排序后相邻二元组是否相等，即赋排名时若该二元组与上一个二元组相同，则排名等于上一个二元组的排名，否则排名等于上一个二元组的排名 \(+1\)。
终于，我们解决了后缀排序问题。
代码
#include<bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
#define timeused() (double)clock()/CLOCKS_PER_SEC
#define rep(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define repp(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define mp make_pair
#define pb push_back
typedef int ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x){
T f=1;x=0;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
x*=f;
return x;
}
string s;
ll n,rk[4000005],nw[1000005],sa[1000005];
ll a[1000005],tp[1000005];
void sufsrt(){
rep(i,0,200) a[i]=0;
rep(i,1,n) ++a[(ll)s[i]];
rep(i,1,200) a[i]+=a[i-1];
repp(i,n,1) sa[a[(ll)s[i]]--]=i;
rk[sa[1]]=1;
rep(i,2,n){
rk[sa[i]]=rk[sa[i-1]];
if(s[sa[i]]!=s[sa[i-1]]) ++rk[sa[i]];
}
for(int i=1;(1<<(i-1))<=n;++i){
rep(j,0,n) a[j]=0;
rep(j,1,n) ++a[rk[j+(1<<(i-1))]];
rep(j,1,n) a[j]+=a[j-1];
rep(j,1,n) tp[a[rk[j+(1<<(i-1))]]--]=j;
rep(j,0,n) a[j]=0;
rep(j,1,n) ++a[rk[j]];
rep(j,1,n) a[j]+=a[j-1];
repp(j,n,1) sa[a[rk[tp[j]]]--]=tp[j];
nw[sa[1]]=1;
rep(j,2,n){
nw[sa[j]]=nw[sa[j-1]]+1;
if(rk[sa[j-1]]==rk[sa[j]]&&rk[sa[j-1]+(1<<(i-1))]==rk[sa[j]+(1<<(i-1))]) --nw[sa[j]];
}
rep(j,1,n) rk[j]=nw[j];
}
}
int main(){
cin>>s;
n=s.size();
s=' '+s;
sufsrt();
rep(i,1,n) printf("%d ",sa[i]);
}