一、算法简介

后缀数组是一种根据字典序将后缀排序的数组。

其求法主要有 O(nlogn) 的倍增法与 O(n) 的DC3算法。

其实听说skew算法也能做

二、实现原理

1.倍增法

设目前已经将 [i,i+2m−1−1](i∈[1,n]) 的子串排好序，

则对于长度为 2m 的子串，发现其覆盖范围为 [i,i+2m−1] 。

而对于前半部分，已经在上一轮倍增时排好序，因此只需要再根据 [i+2m−1,i+2m−1] 部分的字典序进行排序即可。

由于只有两个关键字，可以使用 O(n) 的基数排序。

每次处理好后再将排好的数组倍增，直到完全排好序为止。

2.DC3

还不会，以后再补

三、具体实现

1.倍增法

设 xi​ 与 yi​ 分别表示目前排序时的第一、第二关键字，s 为字符串，sai​ 表示排名为 i 的子串的位置。

(1).预处理

在处理原串时，子串长度为 1，因此 xi​=si​,yi​=i，直接按照其字典序大小进行排序即可。

(2).倍增部分

设当前倍增时长度为 m，每次倍增时，对于 [∣s∣−m+1,∣s∣] 的部分来讲，其后半部分不足以进行倍增，因此第二关键字更小，直接按顺序加入第二关键字即可。

而对于 [1,∣s∣−m] 的部分，其第一关键字已经有序的情况下，只需要将第一关键字加入桶中，照第二关键字排序即可。

处理完后重新进行第一关键字的排序，令 yi​=xi​ ，只要判断是否相同即可知道第一关键字排名。

2.DC3

没学。

四、复杂度证明

对于倍增法，直到完全排序时一共排序了 O(logn) 次，每次排序 O(n)，因此复杂度为 O(nlogn)。

对于DC3，没学。

五、其他

记得桶开大一点，本人桶开小了拍了10k+数据没拍出来错......

六、代码

以P3809 【模板】后缀排序 为例

#include<iostream>
#include<string.h>
using namespace std;
const int MAXN=1000005;
int a,b,c,cnt=0;
int sa[MAXN];
int n1[MAXN],n2[MAXN],num[MAXN];
inline int read()
{
    char x=getchar();int t=0;
    while(!isdigit(x))x=getchar();
    while(isdigit(x))t=(t<<3)+(t<<1)+(x^48),x=getchar();
    return t;
}
void jsort()
{
    for(int i=1;i<=b;++i)num[i]=0;//桶
    for(int i=1;i<=a;++i)num[n1[i]]++;//第一关键字
    for(int i=2;i<=b;++i)num[i]+=num[i-1];//前缀和
    for(int i=a;i>=1;--i)sa[num[n1[n2[i]]]--]=n2[i];
}
int main()
{
    string x;cin>>x;
    a=x.size();
    for(int i=1;i<=a;++i)n1[i]=x[i-1],n2[i]=i;
    b=122;
    jsort();
    for(int k=1;k<=a;k<<=1)
    {
        cnt=0;
        for(int i=a-k+1;i<=a;++i)n2[++cnt]=i;//第二关键字极小
        for(int i=1;i<=a;++i)if(sa[i]>k)n2[++cnt]=sa[i]-k;//第二关键字排序
        jsort();
        for(int i=1;i<=a;++i)n2[i]=n1[i];
        n1[sa[1]]=cnt=1;
        for(int i=2;i<=a;++i)
        {
            if(n2[sa[i]]==n2[sa[i-1]]&&n2[sa[i]+k]==n2[sa[i-1]+k])n1[sa[i]]=cnt;
            else n1[sa[i]]=++cnt;
        }
        if(cnt==a)break;
        b=cnt;
    }
    for(int i=1;i<=a;++i)printf("%d ",sa[i]);
    return 0;
}