后缀数组详解：
这里大概是对后缀数组的代码进行一下解读：
考虑现在想对长度为 $2L$ 的所有串进行排序，而我们已经得到长度为 $L$ 的所有串的相对排名.
$k$ 表示当前要排序串长的半径大小（即上一轮排完的长度).
$tp[i]$ 表示排名为 $i$ 的第二关键字对应的第一关键字的开头.
$rk[i]$ 表示位置 $i$ 的排名.
$sa[i]$ 表示排名为 $i$ 对应的串的位置.
$tp[i]$ 表示排名为 $i$ 的第二关键字对应的第一关键字的开头.
$rk[i]$ 表示位置 $i$ 的排名.
$sa[i]$ 表示排名为 $i$ 对应的串的位置.
$C[i]$ 表示名次 $i$ 及 $i$ 前的字符串数量.
基数排序
void qsort()
{
for(int i = 0; i <= m ; ++i) C[i] = 0;
for(int i = 1; i <= n ; ++i) ++C[rk[i]];
for(int i = 1; i <= m ; ++i) C[i] += C[i - 1];
for(int i = n; i >= 1 ; --i) sa[C[rk[tp[i]]]--] = tp[i];
}
第四个循环比较难懂.
我们采用倒序枚举的方式来枚举每一个第二关键字的排名.
我们已经求得每个第二关键字对应到的第一关键字的位置了.
那么，对于上一轮排名相同的第一关键字来说， 由于已经按照第二关键字先排序一遍，并倒序进行插入了，所以就一定能保证第二关键字
大的排名更大了!!!!
但是我们仔细思考，这样排名有一个问题.
那就是可能有若干串的第一关键字与第二关键字都对应相同，然而我们的排名系统却并没有把它们算成相同的排名.
我们得到 $sa[i]$ 数组后我们想进一步求得 $rk[i]$ 数组.
然而，我们现在有的信息只是上一轮的 $rk'[i]$ 数组与该轮的 $sa[i]$ 数组.
我们考虑如何解决上述不正确的情况.
不难发现所有第一二关键字都对应相同的串在 $sa[i]$ 数组中一定是连续出现的.
所以我们只需判一下第一关键与第二关键字的 $rk'[i]$ 值对不对应相等即可.
Code:
#include <bits/stdc++.h>
#define maxn 5000000
#define setIO(s) freopen(s".in", "r" , stdin)
using namespace std;
namespace SA
{
char str[maxn];
int arr[maxn], C[maxn], rk[maxn], sa[maxn], tp[maxn];
int n, m;
void qsort()
{
for(int i = 0; i <= m ; ++i) C[i] = 0;
for(int i = 1; i <= n ; ++i) ++C[rk[i]];
for(int i = 1; i <= m ; ++i) C[i] += C[i - 1];
for(int i = n; i >= 1 ; --i) sa[C[rk[tp[i]]]--] = tp[i];
}
void Build()
{
for(int i = 1; i <= n ; ++i) arr[i] = str[i];
for(int i = 1; i <= n ; ++i) rk[i] = arr[i], tp[i] = i;
qsort();
for(int k = 1; k <= n ; k <<= 1)
{
int p = 0;
for(int i = n - k + 1; i <= n ; ++i) tp[++p] = i;
for(int i = 1; i <= n ; ++i) if(sa[i] > k) tp[++p] = sa[i] - k;
qsort(), swap(rk, tp);
rk[sa[1]] = 1, p = 1;
for(int i = 2; i <= n ; ++i)
{
rk[sa[i]] = (tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + k] == tp[sa[i] + k]) ? p : ++p;
}
if(p == n) break;
m = p;
}
}
};
int main()
{
// setIO("input");
scanf("%s",SA::str + 1), SA::n = strlen(SA::str + 1), SA::m = 122, SA :: Build();
for(int i = 1; i <= SA::n ; ++i) printf("%d ",SA::sa[i]);
return 0;
}