定义

• 后缀 i ：一个字符串从第 i 个字符到结尾的子串成为这个字符串的后缀 i ；

• 后缀排序：将一个字符串的所有后缀按字典序排序；

• sa[i] ：后缀排序后排名第 i 的后缀；

• rank[i] ：后缀排序后后缀 i 的排名；

• 最长公共前缀（LCP）：两个字符串从头开始最长公共子串的长度；

• height[i] ：后缀 sa[i] 与后缀 sa[i-1] 的 LCP ；

后缀排序

后缀排序就是求解 sa 数组和 rank 数组的过程。

先考虑暴力的方法。快排（ O(NlogN) ）对所有后缀进行排序，但后缀的长度与串长 N 同阶，所以每次比较的时间复杂度就是 O(N) ，总时间复杂度为 O(N^2logN) 。以下是快排版本的代码：

#include <cstdio>
#include <cstring>
const int MAXN=110000;
char a[MAXN];
int n;
int suff[MAXN];
bool cmp(int x, int y)
{
    for (int i=0; x+i<=n&&y+i<=n; i++)
        if (a[x+i]!=a[y+i]) return a[x+i]<a[y+i];
    return x>y;
}
void qsort(int l, int r)
{
    int i=l, j=r, mid=suff[l+r>>1];
    while (i<=j)
    {
        while (cmp(suff[i], mid)) i++;
        while (cmp(mid, suff[j])) j--;
        if (i<=j)
        {
            int t=suff[i];
            suff[i]=suff[j];
            suff[j]=t;
            i++; j--;
        }
    }
    if (l<j) qsort(l, j);
    if (i<r) qsort(i, r);
}
int main()
{
//  freopen("sa.in", "r", stdin);
//  freopen("sa.out", "w", stdout);
    scanf("%s", a+1);
    n=strlen(a+1);
    for (int i=1; i<=n; i++) suff[i]=i;
    qsort(1, n);
    for (int i=1; i<=n; i++)
    {
        for (int j=suff[i]; j<=n; j++)
            putchar(a[j]);
        putchar('\n');
    }
    return 0;
}

但这种算法效率明显不高，最多只能跑 N=1000 左右的数据。我们要想办法改进。

常见的后缀排序算法有 倍增 和 DC3 算法，这里主要介绍基于 倍增 的算法。

现在思考一个问题：假设我们已经完成了对所有子串 [i, i+p) 的排序，现在要进行对子串 [i, i+2p) 的排序，该怎么办呢？

根据上一轮的排序，我们已经知道了子串 [i, i+p) 和子串 [i+p, i+2p) 的排名，就能使用基数排序推出子串 [i, i+2p) 的排名。

对于这个基数排序的理解，可以用类比的思想，将每个长度为 2p 的子串看做一个两位数，把前 p 个字符在上一次排序中的排名视为这个两位数十位上的数字，把后 p 个字符在上一次排序中的排名视为这个两位数个位上的数字，对这些两位数排序即可。为个位和十位各开一个桶，先对个位数进行排序，然后再以个位排序的结果为顺序插入十位的桶中，保证十位数字从小到大排序，且若几个两位数的十位数字相等，则它们个位数字的顺序依然是从小到大的（可以理解为一种稳定排序）。按这样的思路，每次倍增时将 p 翻一倍即可。在排序过程中，可能会存在有两个子串完全相同的情况，这种情况下规定这两个子串的排名也一样（类似于成绩排名，如果有两个人的分数相等且都是最高分，则这两人都是第 1 名，而排在这两人后面的就是第 2 名）。设最后一名的名次为 k ，若 k=n 则说明没有相同的子串，我们就完成了对所有后缀的排序（因为每个后缀的长度都不同，所以一定没有两个相同的后缀）。

这一部分的代码：

// 初始化
// 这一部分主要是把所有长度为 1 的子串的排名求出来，相当于初值，直接桶排序即可
memset(st, 0, sizeof st);
memset(rank, 0, sizeof rank);
memset(rank1, 0, sizeof rank1);
for (int i=1; i<=n; i++) st[a[i]]=1;
for (int i=1; i<256; i++) st[i]+=st[i-1];
for (int i=1; i<=n; i++) rank[i]=st[a[i]];

for (int k=0, p=1; k!=n; p<<=1)
{
    // 对第一关键字排序
    memset(count, 0, sizeof count);
    for (int i=1; i<=n; i++) count[rank[i+p]]++;
    for (int i=1; i<=n; i++) count[i]+=count[i-1];
    for (int i=n; i>=1; i--) tmp[count[rank[i+p]]--]=i;
    // 这里的 tmp[i] 表示排名第 i 的子串是 [tmp[i]+p, tmp[i]+2*p)

    // 对第二关键字排序
    memset(count, 0, sizeof count);
    for (int i=1; i<=n; i++) count[rank[i]]++;
    for (int i=1; i<=n; i++) count[i]+=count[i-1];
    for (int i=n; i>=1; i--) sa[count[rank[tmp[i]]]--]=tmp[i];
    // 这里一定记得按 tmp 的反向顺序收集 count 数组

    // 计算排名
    memcpy(rank1, rank, sizeof rank1);
    rank[sa[1]]=k=1;
    for (int i=2; i<=n; i++)
    {
        if (rank1[sa[i]]!=rank1[sa[i-1]]
          ||rank1[sa[i]+p]!=rank1[sa[i-1]+p]) k++;
        // 如果第 i 名与第 i-1 名不同，则当前名次+1
        rank[sa[i]]=k;
    }
}