$$后缀数组$$

$引入$

对于一个字符串，后缀 $i$ 表示以第 $i$ 个字符开头的后缀，即 $s[i,n]$。

要求给所有的后缀 $i(1 \leq i\leq n)$ 排序

$定义$

$sa[i]$ 表示当前排名为 $i$ 的字符串的开头下标。

$rk[i]$ 表示以第 $i$ 个字符开头的后缀的排名。

$思路$

运用倍增算法

对后缀长度 $k$ 倍增。

对所有以 $i(1\leq i \leq n)$ 开头，长度为 $k$ 的字符串排序(超出部分用空格补足，空格小于所有字符)。

用长度 $k$ 的排序结果推长度为 $2k$ 的排序结果。

对于 $i(1\leq i\leq n)$ 来说，以第$i$个字符开头长度 $k$ 的字符串排名作为第一关键字，以第 $i+k$ 个字符开头长度 $k$ 的字符串排名作为第二关键字(第一关键字可能用相同，所以用第二关键字区分)。

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;
    }
}

$height数组$

$height[i] = lcp(sa[i], sa[i-1])$，$lcp$ 指最长公共前缀 $(height[1] = 0)$。

引理：$height[rk[i]] \ge height[rk[i - 1]] - 1$

当 $height[rk[i - 1]] \leq 1$ 时，不等式一定成立，所以考虑 $height[rk[i - 1]] > 1$。

将后缀 $i - 1$ 表示为 $cAB$，则 $sa[rk[i - 1] - 1]$ 表示为 $cAD$，公共最长前缀为 $cA$。

后缀 $i$ 同理表示为 $AB$。

由于有后缀 $cAD$，那么一定有后缀 $AD$。

$\therefore height[i] \ge lcp(AB, AD) = height[rk[i - 1]] - 1$

证毕。

有了引理，直接暴力就可以做到 $O(n)$ 的复杂度。

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;
    }
}

$后缀数组实现$

#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;

int n, m;
char s[N];
int sa[N], rk[N], x[N], y[N], height[N], c[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]);

    return 0;
}