AI Summary
介绍后缀数组sa与rk及四种复杂度求法，附洛谷P3809代码和题单链接。
基础知识
后缀数组（Suffix Array）主要关系到两个数组： 和 ．
其中， 表示将所有后缀排序后第 小的后缀的编号，也是所说的后缀数组，后文也称编号数组 ；
表示后缀 的排名，是重要的辅助数组，后文也称排名数组 。
这两个数组满足性质： 。
存在 ，，， 的求法。
对于 做法，直接给所有后缀串排序即可。排序复杂度 ，字符串比较 。
对于 ，用到倍增思想，排序复杂度 ，倍增比较 。1
对上述方法进行基数排序优化，可以优化到 。
例题（题单第一题） 后缀排序(洛谷-P3809)代码，使用 复杂度算法：
/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define szof sizeof
intc N=1e6+10;
string s;
int n,m=127,sa[N],rk[N<<1],prk[N<<1],id[N],cnt[N];
signed main() {
Cios;
cin>>s;
n=s.size();
s="&"+s;
for (int i=1;i<=n;i++) cnt[rk[i]=s[i]]++;
for (int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for (int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;
memcpy(prk+1,rk+1,n*szof(int));
for (int p=0,i=1;i<=n;i++) {
if (prk[sa[i]]==prk[sa[i-1]]) rk[sa[i]]=p;
else rk[sa[i]]=++p;
}
for (int w=1;w<n;w<<=1,m=n) {
memset(cnt,0,szof cnt);
memcpy(id+1,sa+1,n*szof(int));
for (int i=1;i<=n;i++) cnt[rk[id[i]+w]]++;
for (int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for (int i=n;i>=1;i--) sa[cnt[rk[id[i]+w]]--]=id[i];
memset(cnt,0,szof cnt);
memcpy(id+1,sa+1,n*szof(int));
for (int i=1;i<=n;i++) cnt[rk[id[i]]]++;
for (int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
for (int i=n;i>=1;i--) sa[cnt[rk[id[i]]]--]=id[i];
memcpy(prk+1,rk+1,n*szof(int));
for (int p=0,i=1;i<=n;i++) {
if (prk[sa[i]]==prk[sa[i-1]]&&prk[sa[i]+w]==prk[sa[i-1]+w]) rk[sa[i]]=p;
else rk[sa[i]]=++p;
}
}
for (int i=1;i<=n;i++) cout<<sa[i]<<" \n"[i==n];
return 0;
}
评论（2）