话不多说放题。
后缀排序是在求后缀数组 sa。
我们还需要一个 rk 数组计入排名，最后就可以用 rk 求出 sa 了。
假设有一个串wzhtql（顺带%一下）。
步骤如下，第一步将每个字符排序，结果如下。
w z h t q l
5 6 1 4 3 2
\begin{bmatrix}
w& z &h &t &q&l \\
5&6 &1 &4 &3 & 2
\end{bmatrix}
可以看到没有相同的了，可以结束了，但是我们把流程走完。
接下来倍增，每个数和后面第一个数接起来，如果后面每这个数用 0 代替。
\begin{bmatrix}
w& z &h &t &q&l \\
56&61 &14 &43 &32 & 20
\end{bmatrix}
然后将这些数字排序。
这样接下来就是后面第二个不断倍增。
这个例子可能不太明显，换了例子：wzhwzh。
先排序。
\begin{bmatrix}
w& z &h &w &z&h \\
3&1 &5 &3 &1 & 5
\end{bmatrix}
然后：
\begin{bmatrix}
w& z &h &w &z&h \\
31&15 &53 &31 &15 & 50
\end{bmatrix}
再排序，不断倍增：
\begin{bmatrix}
w& z &h &w &z&h \\
3&1 &6 &3 &1 & 5\\
35&13 &61 &35 &10 & 50\\
3&2 &6 &3 &1 & 5\\
31&25 &60 &30 &10 & 50\\
4&2 &6 &3 &1 & 5
\end{bmatrix}
所以最终的 rk 数组就求出来了，没看懂的可以多看几遍，正确性请自行证明，没啥难的。
那怎么排序呢：
直接快排是 O(n\log^{2}n) 。
也可以用基数排序，比快排快点： O(nk\log n) ， k 大概是 13 ，快排的一个 \log 是20，差了一半不到。
最快的是用计数排序是 O(n\log n) 的不过常数有 8 左右，比快排快了一倍。
编码应该挺简单的，给一个求 rk 数组的过程，怎么从 rk 转化成 sa 请自行思考。
void calc_sa()
{
a[0].x=-1;
sort(a+1,a+1+n,cmp);
int sum=-1;
for(int i=1;i<=n;++i)
if(a[i].x==a[i-1].x) rk[a[i].id]=sum;
else
{
sum++;
rk[a[i].id]=sum;
}
for(int k=1;k<=n;k*=2)
{
for(int i=1;i<=n;++i)
{
if(i+k>n) a[i].x=1ll*rk[i]*N;
else a[i].x=1ll*rk[i]*N+rk[i+k];
a[i].id=i;
}
sort(a+1,a+1+n,cmp);
sum=-1;
for(int i=1;i<=n;++i)
if(a[i].x==a[i-1].x) rk[a[i].id]=sum;
else
{
sum++;
rk[a[i].id]=sum;
}
}
}
我用的是快排有点卡常，想要更快可以用基数和计数两个排序。
