定义\(sa_i\)表示排名为 \(i\) 的后缀编号是什么。
例：\(ababa\)
\(sa_1=5,sa_2=3,sa_3=1,sa_4=4,sa_5=2\)
思路理解：
先根据第一位排序，确定最初的\(sa\)
for(ll i=1;i<=n;i++) ++c[x[i]=s[i]];
for(ll i=2;i<=m;i++) c[i]+=c[i-1];
for(ll i=n;i>=1;i--) sa[c[x[i]]--]=i;
先用桶排，确定每个字符有多少个(第一行数组\(c\))，再用前缀和(第二行数组\(c\))，确定字典序小于等于这个字符的字符个数，最后再用\(c\)确定数组\(sa\)(注：第一位相同时，位置越后，排名越后)
然后考虑倍增（为什么倍增可以我也不知道）
for(ll k=1;k<=n;k<<=1)
然后用基数排序的思想，在第一关键字的基础上，用第二关键字排序
定义\(y_i\)为排名为第 \(i\) 的第二关键字
然后根据上次排序的\(sa\)来确定\(y\)
ll num=0;
for(ll i=n-k+1;i<=n;i++) y[++num]=i;
for(ll i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
首先，因为后\(k\)位是没有第二关键字的，所以按照字典序他们的第二关键字最小，所以直接存在于\(y\)中。
否则若排名为\(i\)的后缀可作为其他位置的第二关键字，即\(sa_i>k\)，就把他放在对应的第一关键字(\(x_{sa_i-k}\))中
然后从后往前更新\(sa\)
for(int i=1;i<=m;i++)c[i]=0;
for(int i=1;i<=n;i++)c[x[i]]++;
for(int i=2;i<=m;i++)c[i]+=c[i-1];
for(int i=n;i>=1;i--){sa[c[x[y[i]]]--]=y[i];y[i]=0;}
最后，更新\(x_i\)
swap(x,y);
num=1;x[sa[1]]=1;
for(int i=2;i<=n;i++)
{
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=num;
else x[sa[i]]=++num;
}
这里一起讲：
除第一次外(因为第一次是在循环外更新\(x_i\)，即按照第一关键字排序)，其他都是在循环内更新\(x_i\)
我们在上一次循环中已经更新了第一关键字了，所以只需要根据第二关键字更新排名即可，即
for(int i=n;i>=1;i--){sa[c[x[y[i]]]--]=y[i];y[i]=0;}
然后，因为在本次循环中，已经更新完了\(y_i\)，所以在下一次循环中，\(x_i\)和\(y_i\)将一同作为第一关键字出现 ，那么下一个循环中的第一关键字相同的条件为\(x_i=x_j\)并且\(y_i=y_j\)
最后说一下为什么从后往前：因为前面的\(1\)~\(k\)的数已经是没有第二关键字了，按照字典序他们应该在第一关键字相同的所有后缀中的最前面，所以让他们最后被处理，即从后往前排序
例如：
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1114514;
char s[N];
ll c[N],x[N],sa[N],y[N];
ll n,m;
void get_SA()
{
for(ll i=1;i<=n;i++) ++c[x[i]=s[i]];
for(ll i=2;i<=m;i++) c[i]+=c[i-1];
for(ll i=n;i>=1;i--) sa[c[x[i]]--]=i;
for(ll k=1;k<=n;k<<=1)
{
ll num=0;
for(ll i=n-k+1;i<=n;i++) y[++num]=i;
for(ll i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
for(ll i=1;i<=m;i++) c[i]=0;
for(ll i=1;i<=n;i++) ++c[x[i]];
for(ll i=2;i<=m;i++) c[i]+=c[i-1];
for(ll i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];
swap(x,y);
x[sa[1]]=1;
num=1;
for(ll i=2;i<=n;i++)
{
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=num;
else x[sa[i]]=++num;
}
if(num==n) break;
m=num;
}
for(ll i=1;i<=n;i++)
printf("%lld ",sa[i]);
puts("");
}
int main()
{
cin>>s+1;
n=strlen(s+1),m=122;
get_SA();
return 0;
}