三大数组:

$Sa[i]$ : 排名第$i$位的是第几个后缀.

$rk[i]$ : 第 $i$个后缀的排名是多少.

$height[i]$ : $sa[i]$和$sa[i-1]$ ,的最长公共前缀.

基础定义:

后缀 $S[i]：S[i] = S[i, |S|]$

字典序：对于两个字符串 $S$ 和 $T$，从左到右找到第一个不同的字母，谁

的字母小，谁的字典序就小。特殊的，如果$S$为 $T$ 的前缀，认为 $S \lt T$。即空字符最小。

前缀倍增法求后缀数组

思路：将比较字典序的二分求 $LCP$ 转化为倍增求 $LCP$。

首先等效的认为在字符串的末尾增添无限个空字符 $∅$ 。

定义 $S(i, k) = S[i, i + 2k − 1]$ ，即以 i 位置开头，长度为 $2k$ 的子串。

后缀 $S[i]$ 与 $S[j]$ 的字典序关系等价于 $S(i, ∞)$ 与 $S(j, ∞)$的字典序关系。

事实上，只需要将 $S(i, ⌈log2n⌉)，i = 1, 2, · · · , n$ 排序即可。

复杂度分析：

算法需要运行 $log n$ 轮。每一轮使用基数排序，复杂度为 $O(n)$。

整体复杂度为 $O(n log n)$。

模板 Code:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n, m;
char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];

void get_sa()
{
    for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ;
    for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
    for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i;
    for (int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for (int i = n - k + 1; i <= n; i ++ ) y[ ++ num] = i;
        for (int i = 1; i <= n; i ++ )
            if (sa[i] > k)
                y[ ++ num] = sa[i] - k;
        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; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i ++ )
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if (num == n) break;
        m = num;
    }
}

void get_height()
{
    for (int i = 1; i <= n; i ++ ) rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; i ++ )
    {
        if (rk[i] == 1) continue;
        if (k) k -- ;
        int j = sa[rk[i] - 1];
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++ ;
        height[rk[i]] = k;
    }
}

int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1), m = 122;
    get_sa();
    get_height();

    for (int i = 1; i <= n; i ++ ) printf("%d ", sa[i]);
    puts("");
    for (int i = 1; i <= n; i ++ ) printf("%d ", height[i]);
    puts("");
    return 0;
}