后缀数组

形式化题目

给定长度为 $n$ 的小写字母串 $S$ （下标 $0 \sim n-1$ ）。对每个 $0 \leqslant k < n$ ，记后缀 $S_k = S[k \sim n-1]$ 。

把所有 $n$ 个后缀按字典序从小到大排序，排名为 $i$ 的后缀的起始下标记为 $SA[i]$ （ $i$ 从 $0$ 开始）。
令 $Height[i]$ 表示排名 $i$ 的后缀与排名 $i-1$ 的后缀的最长公共前缀长度；排名 $0$ 的后缀没有前一个，规定 $Height[0] = 0$ 。

要求输出 $SA$ 与 $Height$ 两个长度为 $n$ 的数组。 $n \leqslant 3 \times 10^5$ ，字符集为 26 个小写字母。

以样例 ponoiiipoi 为例，按字典序排好之后， $SA$ 与 $Height$ 的含义是：

排名 $i$	$SA[i]$	后缀 $S[SA[i] \sim ]$	$Height[i]$	与哪个后缀取公共前缀
0	9	`i`	0	规定为 0
1	4	`iiipoi`	1	`i`
2	5	`iipoi`	2	`iiipoi`
3	6	`ipoi`	1	`iipoi`
4	2	`noiiipoi`	0	`ipoi`
5	8	`oi`	0	`noiiipoi`
6	3	`oiiipoi`	2	`oi`
7	1	`onoiiipoi`	1	`oiiipoi`
8	7	`poi`	0	`onoiiipoi`
9	0	`ponoiiipoi`	2	`poi`

表中第 4 列是本题要求的 $Height$ ，注意 $Height[0]$ 是人为规定的 0，其余各项都是排名相邻的两个后缀真正共有的前缀长度。

正解

思路

为什么不能逐对比较。 最直接的做法是用 sorted(range(n), key=lambda i: S[i:])：排序需要 $O(n \log n)$ 次比较，而每次比较两个后缀最坏要看到末尾，代价 $O(n)$ ，总时间 $O(n^2 \log n)$ 。 $n = 3\times 10^5$ 时约 $10^{17}$ 次字符比较，不可行。瓶颈不在排序次数，而在每次比较都从头看了太多字符。

观察：两个后缀的字典序只由「前 $2^k$ 个字符的相等关系」决定。 定义 $rank_k[i]$ 为子串 $S[i \sim i+2^k-1]$ 在所有长度为 $2^k$ （不足则取到串尾）的子串中的排名。长度为 $1$ 的前缀就是单个字符，所以 $rank_0$ 可以直接由字符编码得到。把长度翻倍时， $S[i \sim i+2^{k+1}-1]$ 就是 $S[i \sim i+2^k-1]$ 接上 $S[i+2^k \sim i+2^{k+1}-1]$ ，于是

S[i \sim i+2^{k+1}-1] < S[j \sim j+2^{k+1}-1] \iff (rank_k[i],\, rank_k[i+2^k]) < (rank_k[j],\, rank_k[j+2^k])

按两关键字排序即可。第 2 个关键字越界时（ $i + 2^k \geqslant n$ ）读哨兵 $-1$ ，因为 $-1$ 小于任何真实排名，短后缀自然排在长后缀前面——这正是字典序要的顺序。

什么时候可以停。 如果某一轮结束后最大排名恰好等于 $n-1$ ，说明 $n$ 个排名两两不同，所有后缀的前 $2^{k+1}$ 个字符已经能区分彼此，再翻倍也不会改变顺序， $SA$ 就是最终答案。 $k$ 从 $0$ 开始每轮翻倍，最多 $\lceil \log_2 n \rceil + 1$ 轮。

下面用样例的前两轮说明这个过程。表中每次「排序」都按 (前半段排名, 后半段排名) 双关键字进行，「重编号」把相同关键字组合合并成同一个新排名：

轮次	子串 $SA$ 的候选顺序	前半段排名	后半段排名	重编号后的 $rank$ （按下标）
初始（ $1$ 字符）	`0 1 2 3 4 5 6 7 8 9`	—	—	`112 111 110 111 105 105 105 112 111 105`
第 1 轮（ $2$ 字符）	`9 4 5 6 2 3 8 1 0 7`	`105 105 105 105 110 111 111 111 112 112`	`-1 105 105 112 111 105 105 110 111 111`	`6 5 3 4 1 1 2 6 4 0`
第 2 轮（ $4$ 字符）	`9 4 5 6 2 8 3 1 7 0`	`0 1 1 2 3 4 4 5 6 6`	`-1 2 6 4 1 -1 1 4 0 3`	`9 7 4 6 1 2 3 8 5 0`

第 2 轮的最大排名是 $9 = n-1$ ，顺序已经唯一确定，于是停止， $SA = [9,4,5,6,2,8,3,1,7,0]$ ，与样例一致。注意初始时 $rank$ 里存的是字符编码（'a' 是 $97$ ）而不是 $0 \sim 25$ 的编号，这只影响可读性，不影响相对大小，也不影响后面「最大排名是否等于 $n-1$ 」的判断——判断的依据是每轮重编号后的结果。

$Height$ 怎么算。 逐对求 LCP 又要回退到 $O(n^2)$ 的字符比较，但上面保留下来的 $rank_k$ 表恰好是现成的 LCP 工具。设字典序相邻的两个后缀起点为 $lo < hi$ ，已经确定的公共前缀长度为 $h$ ；如果

rank_k[lo + h] = rank_k[hi + h]

就说明从位置 $h$ 开始的长度为 $2^k$ 的两段内容完全相同，于是 $h$ 可以安全地加上 $2^k$ 。把 $k$ 从大到小扫一遍，每层能加就加，最后得到的 $h$ 就是 LCP：从上往下贪心等价于把答案做二进制分解，高位能放就放，所以结果正好是实际长度。长度越界时读到的是哨兵 $-1$ ，两个都越界则排名同为 $-1$ ，但此时公共前缀不可能真的延伸到串尾之后，这也保证 $h$ 不会超过两后缀的较短长度（越界处对应的子串已经短于 $2^k$ ，不可能与另一个等长）。

Python 侧的实现选择。 每轮的主要工作是「按两个关键字排序 $n$ 个下标」和「重编号」，都是对整数组的操作。纯 Python 的 sorted 每轮要搬 30 万个元素并做大量比较， $\log n \approx 19$ 轮下来代价很高；这里把每轮写成 np.lexsort + np.cumsum，排序和重编号都在 C 层完成。排名和下标的取值范围都不超过 $3\times10^5$ ，用 int32 可以让保存各轮排名的 levels 表省一半内存；levels 在算完 $Height$ 后立刻 del，避免和输出字符串峰值叠加。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 11:55
# update_at: 2026-10-01 11:55

# 30 万的后缀数组，纯 Python 的倍增排序每轮都要自己搬 30 万个元素，代价太高；
# 每一轮「排序 + 重排名」正好是两次全数组操作，交给 numpy 做向量化最划算。
# 排名和下标的取值范围都小于 2^31，统一用 int32，levels 表能省一半内存。

import sys

import numpy as np

END = -1  # 后缀末尾的哨兵排名：比任何真实字符都小，越界部分自动排到最短后缀之后


def suffix_array(s: bytes, length: int) -> tuple[np.ndarray, list[np.ndarray]]:
    """倍增求后缀数组：返回 (SA, levels)，其中 levels[k][i] 是子串 s[i:i+2^k] 的排名。

    每轮把「按长度 2^k 前缀排名」升级成「按长度 2^{k+1} 前缀排名」：把每个后缀的排名
    拆成 (前半段, 后半段) 两个关键字重新排序。后半段越界时读哨兵，于是所有短后缀
    在字典序里天然排在长后缀之前。
    """
    rank = np.empty(length + 1, dtype=np.int32)         # 末位留给下标 length 的哨兵
    rank[:length] = np.frombuffer(s, dtype=np.uint8)    # 长度 1 的前缀就是单个字符
    rank[length] = END
    sa = np.arange(length, dtype=np.int32)
    levels = [rank]
    step = 1                                            # 已经排好的前缀长度 2^k
    while step < length:
        second = rank[np.minimum(sa + step, length)]    # 后半段排名，越界取哨兵
        order = np.lexsort((second, rank[sa]))          # rank[sa] 是主关键字，second 是次关键字
        sa = sa[order]
        head, tail = rank[sa], second[order]
        differs = (head[1:] != head[:-1]) | (tail[1:] != tail[:-1])
        merged = np.concatenate((np.zeros(1, dtype=np.int32), np.cumsum(differs, dtype=np.int32)))
        rank = np.empty(length + 1, dtype=np.int32)     # 新排名仍按下标存放
        rank[sa] = merged                               # 合并后的次序是「排名第 i 小的下标」
        rank[length] = END
        levels.append(rank)
        if merged[-1] == length - 1:                    # 最大合并排名 = length-1 说明后缀顺序已唯一
            break
        step <<= 1
    return sa, levels


def lcp_array(sa: np.ndarray, levels: list[np.ndarray]) -> np.ndarray:
    """相邻后缀的最长公共前缀长度，即 Height 数组，返回值第 0 位固定为 0。

    字典序相邻的两个后缀，设它们起点为 lo < hi：它们的公共前缀长度可以按 2 的幂
    从大到小拼出来——只要「从当前长度再往后 2^k 个字符」这一段在 levels 表里排名
    相同，就说明这一段确实相等，可以放心把 2^k 加进答案。
    """
    lo, hi = np.minimum(sa[:-1], sa[1:]), np.maximum(sa[:-1], sa[1:])
    height = np.zeros(len(lo), dtype=np.int32)
    for k in range(len(levels) - 1, -1, -1):
        hit = levels[k][lo + height] == levels[k][hi + height]
        height += np.where(hit, 1 << k, 0)
    return np.concatenate((np.zeros(1, dtype=np.int32), height))


def solve() -> None:
    s = sys.stdin.buffer.read().strip()                 # 题目保证只有小写字母，strip 掉末尾换行即可
    sa, levels = suffix_array(s, len(s))
    height = lcp_array(sa, levels)
    del levels                                          # 倍增过程的排名表只给 LCP 用，输出前释放
    write = sys.stdout.write
    for arr in (sa, height):
        write(' '.join(map(str, arr.tolist())))
        write('\n')


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:32
 * update_at: 2026-10-06 15:32
 */
#include <cstdio>
#include <cstring>

// 后缀数组（倍增 + 计数排序），n <= 3e5。
// 下标、排名都小于 2^31，统一用 int，数组更省内存、访问更快。

typedef long long ll;

const int MAXN = 300005;

char s[MAXN];           // 输入字符串，下标 0 ~ n-1
int n;                  // 串长
int sa[MAXN];           // sa[i] = 字典序排名第 i 的后缀的起始下标
int rk[MAXN * 2];       // rk[i] = 后缀 i 的排名；后半段预留为 0，充当“越界最小哨兵”
int old_rk[MAXN * 2];   // 上一轮排名，用来比较两关键字是否相同
int id[MAXN];           // 按第二关键字排好序的后缀下标
int cnt[MAXN + 1];      // 计数排序的桶
int height[MAXN];       // height[i] = sa[i] 与 sa[i-1] 的最长公共前缀，height[0] = 0

// 倍增构造 sa：每轮把「长度 w 的排名」升级成「长度 2w 的排名」。
void build_sa() {
    // 第一轮：按单个字符排序，排名从 1 开始，于是 0 天然是比任何真实排名都小的哨兵。
    int m = 256;
    for (int i = 0; i <= m; i++) cnt[i] = 0;
    for (int i = 0; i < n; i++) {
        rk[i] = (unsigned char)s[i] + 1;
        cnt[rk[i]]++;
    }
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[i]]] = i;

    for (int w = 1;; w <<= 1) {
        // 按第二关键字 rk[i+w] 排序：越界者第二关键字为 0，排最前；其余按上一轮 sa 顺序取出。
        int p = 0;
        for (int i = n - w; i < n; i++) {
            if (i >= 0) id[p++] = i;
        }
        for (int i = 0; i < n; i++) {
            if (sa[i] >= w) id[p++] = sa[i] - w;
        }
        // 按第一关键字 rk 对 id 做稳定计数排序，得到新的 sa。
        for (int i = 0; i <= m; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[rk[id[i]]]++;
        for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[id[i]]]] = id[i];

        // 两个关键字都相同的后缀合并成同一个新排名。
        for (int i = 0; i < n; i++) old_rk[i] = rk[i];
        int classes = 1;
        rk[sa[0]] = 1;
        for (int i = 1; i < n; i++) {
            if (old_rk[sa[i]] != old_rk[sa[i - 1]] ||
                old_rk[sa[i] + w] != old_rk[sa[i - 1] + w]) {
                classes++;
            }
            rk[sa[i]] = classes;
        }
        if (classes == n) break;  // n 个排名两两不同，后缀顺序已经唯一确定
        m = classes;
    }

    // 统一转成 0 基排名，方便后面 Height 的下标运算。
    for (int i = 0; i < n; i++) rk[i]--;
}

// Kasai 算法求 height：利用 height[rk[i]] >= height[rk[i-1]] - 1 的性质线性扫描。
void build_height() {
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (rk[i] == 0) {
            h = 0;
            continue;  // 排名第 0 的后缀没有前一个后缀
        }
        int j = sa[rk[i] - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
        height[rk[i]] = h;
        if (h > 0) h--;
    }
}

int main() {
    if (scanf("%s", s) != 1) return 0;
    n = strlen(s);

    build_sa();
    build_height();

    for (int i = 0; i < n; i++) {
        if (i > 0) printf(" ");
        printf("%d", sa[i]);
    }
    printf("\n");
    for (int i = 0; i < n; i++) {
        if (i > 0) printf(" ");
        printf("%d", height[i]);
    }
    printf("\n");
    return 0;
}

复杂度

设 $n$ 为串长，倍增轮数为 $O(\log n)$ 。

时间：每轮做一次双关键字排序（ $O(n \log n)$ ）加两次线性重编号，共 $O(n \log^2 n)$ ； $Height$ 部分对每一层做一次向量比较，共 $O(n \log n)$ 。整体 $O(n \log^2 n)$ ，与题目提示的「快排 + Hash + 二分」同阶。
空间： $SA$ 与 $Height$ 各 $O(n)$ ，另有 $O(\log n)$ 张长度 $n+1$ 的 int32 排名表，合计 $O(n \log n)$ 。 $n = 3\times10^5$ 时实测峰值约 100 MB。

总结

本题要求实现后缀数组和 $Height$ 数组。核心是把「后缀之间的比较」转成「定长前缀之间的比较」：用倍增让每个后缀的排名由 $2^k$ 长度前缀的排名拼出，排序只需比较两个整数关键字，于是 $O(n^2)$ 的逐字符比较被压到 $O(n \log^2 n)$ 。 $Height$ 不需要另起一套算法——倍增过程中保存的每层排名表本身就是「长度为 $2^k$ 的两段是否相等」的判据，从高位往低位贪心地加就能拼出相邻后缀的 LCP。

在 Python 里，这套算法的每步都是整数组操作，所以用 numpy 向量化（lexsort 双关键字排序、cumsum 重编号）是最直接的落地方式；代价是空间上多了 $O(\log n)$ 张排名表，因此用 int32 并在输出前释放。

目录

形式化题目

正解

思路

代码

复杂度

总结