后缀数组

前言

07-01 字符串哈希 可以在 $O(1)$ 内比较两个子串，但有些问题需要更全局的视角。比如：一个字符串有多少个不同的子串？最长的重复子串是什么？两个字符串的最长公共子串有多长？

这些问题的答案藏在字符串的所有后缀里。把所有后缀按字典序排序，相邻后缀的最长公共前缀（LCP）蕴含了关于重复和不同的全部信息。这个排序后的数组就是后缀数组（Suffix Array, SA）。

问题的本质

什么是后缀数组？

对字符串 $S$ 的每个后缀 $S[i \ldots N-1]$ 按字典序排序。$SA[k]$ = 排第 $k$ 的后缀的起始位置。

比如 $S$ = “abcbcba”：

后缀	起始位置
a	6
abcbcba	0
ba	5
bcba	3
bcbcba	1
cba	4
cbcba	2

$SA = [6, 0, 5, 3, 1, 4, 2]$。

LCP 数组

$LCP[k]$ = $SA[k]$ 和 $SA[k-1]$ 对应后缀的最长公共前缀长度。可以用 Kasai 算法在 $O(N)$ 内从 $SA$ 求出。

LCP 的核心应用：

• 不同子串数 $= \frac{N(N+1)}{2} - \sum_{k=1}^{N-1} LCP[k]$
• 最长重复子串 $= \max_k LCP[k]$

为什么不同子串公式成立？每个后缀 $SA[k]$ 贡献 $N - SA[k]$ 个前缀（即子串），但其中 $LCP[k]$ 个和前一个后缀重复。所以总不同子串数 = 所有后缀的前缀数之和 - 所有重复。

理论 + 代码

SA 的构建（$O(N \log^2 N)$）

竞赛中通常使用 DC3 / SA-IS 算法（$O(N)$），但实现较复杂。这里给出 $O(N \log^2 N)$ 的基于排序的方法，足以处理 $N \le 10^5$。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int N;
char S[500009];
int sa[500009], rank_[500009], tmp[500009];

bool cmp(int i, int j) {
    if (rank_[i] != rank_[j]) return rank_[i] < rank_[j];
    int ri = (i + N/2 < N) ? rank_[i + N/2] : -1;  // ① 第二关键字
    int rj = (j + N/2 < N) ? rank_[j + N/2] : -1;
    return ri < rj;
}

void build_sa() {
    for (int i = 0; i < N; i++) {
        sa[i] = i;
        rank_[i] = S[i];                             // ② 初始按单字符排序
    }
    for (int k = 1; k < N; k *= 2) {                 // ③ 倍增
        sort(sa, sa + N, cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < N; i++)
            tmp[sa[i]] = tmp[sa[i-1]] + cmp(sa[i-1], sa[i]); // ④ 重新编号
        memcpy(rank_, tmp, sizeof(int) * N);
    }
}

逐行解析：

• ② 初始 rank 按字符值。
• ③ 每次把比较长度翻倍。$O(\log N)$ 轮，每轮排序 $O(N \log N)$，总 $O(N \log^2 N)$。
• ④ 如果当前和前一个不同，rank +1。

Kasai 算法求 LCP（$O(N)$）

int lcp[500009];

void build_lcp() {
    for (int i = 0; i < N; i++) rank_[sa[i]] = i;    // ① rank[i] = 后缀 i 在 SA 中的位置
    int h = 0;
    for (int i = 0; i < N; i++) {
        if (rank_[i] > 0) {
            int j = sa[rank_[i] - 1];                 // ② SA 中前一个后缀
            while (i + h < N && j + h < N && S[i+h] == S[j+h]) h++; // ③ 逐字符比较
            lcp[rank_[i]] = h;
            if (h > 0) h--;                           // ④ h 至多减 1
        }
    }
}

逐行解析：

• ① rank_[i] 是后缀 $i$ 在 SA 中的下标。
• ② $j$ 是 SA 中紧邻 $i$ 前面的后缀。
• ③ 从 $h$ 开始比较（利用上一步的结果）。
• ④ 关键优化：下一轮的 LCP 至少是 $h-1$。所以 $h$ 的总增加次数 $\le 2N$，总时间 $O(N)$。

例题

例题 1：ACL I — Number of Substrings（不同子串计数）

题目：给定字符串 $S$，求不同子串的个数。

数据范围：$1 \le |S| \le 5 \times 10^5$

—— AtCoder Library Practice Contest I

分析：经典 SA+LCP 应用。不同子串数 = $\frac{N(N+1)}{2} - \sum LCP[k]$。

ACL Practice 的标准解法是用 ACL 的 suffix_array 和 lcp_array 函数。

输入样例：abcbcba，输出：21

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int N;
char S[500009];
int sa[500009], rank_[500009], tmp[500009], lcp[500009];

bool cmp_sa(int i, int j) {
    if (rank_[i] != rank_[j]) return rank_[i] < rank_[j];
    int ri = (i + N/2 < N) ? rank_[i + N/2] : -1;
    int rj = (j + N/2 < N) ? rank_[j + N/2] : -1;
    return ri < rj;
}

void build_sa() {
    for (int i = 0; i < N; i++) { sa[i] = i; rank_[i] = S[i]; }
    for (int k = 1; k < N; k *= 2) {
        sort(sa, sa + N, cmp_sa);
        tmp[sa[0]] = 0;
        for (int i = 1; i < N; i++)
            tmp[sa[i]] = tmp[sa[i-1]] + cmp_sa(sa[i-1], sa[i]);
        memcpy(rank_, tmp, sizeof(int) * N);
    }
}

void build_lcp() {
    for (int i = 0; i < N; i++) rank_[sa[i]] = i;
    int h = 0;
    for (int i = 0; i < N; i++) {
        if (rank_[i] > 0) {
            int j = sa[rank_[i] - 1];
            while (i + h < N && j + h < N && S[i+h] == S[j+h]) h++;
            lcp[rank_[i]] = h;
            if (h > 0) h--;
        }
    }
}

int main() {
    scanf("%s", S);
    N = strlen(S);
    build_sa();                                      // ① 构建后缀数组
    build_lcp();                                     // ② 构建 LCP 数组

    long long ans = 1LL * N * (N + 1) / 2;           // ③ 所有可能子串数
    for (int i = 1; i < N; i++)
        ans -= lcp[i];                               // ④ 减去重复
    printf("%lld\n", ans);
}

逐行解析：

• ①② $O(N \log^2 N)$ 构建 SA，$O(N)$ 构建 LCP。
• ③ 总子串数 $= 1 + 2 + \ldots + N = N(N+1)/2$。
• ④ 每对相邻后缀的 LCP 长度就是重复的子串数。

验证：$S$ = “abcbcba”，$N=7$。总子串 $= 7 \times 8 / 2 = 28$。

SA = [6,0,5,3,1,4,2]（后缀：a, abcbcba, ba, bcba, bcbcba, cba, cbcba）。

k	SA[k]	后缀	LCP[k]
0	6	a	-
1	0	abcbcba	1 (a)
2	5	ba	0
3	3	bcba	1 (b)
4	1	bcbcba	3 (bcb)
5	4	cba	0
6	2	cbcba	2 (cb)

$\sum LCP = 1+0+1+3+0+2 = 7$。$28 - 7 = 21$。✓

---

例题 2：最长重复子串

场景：给定字符串 $S$，求最长的至少出现两次的子串长度。

数据范围：$1 \le |S| \le 10^5$

分析：最长重复子串 = $\max_k LCP[k]$。SA 中相邻后缀的 LCP 恰好表示这两个后缀共享的最长前缀，也就是最长的重复子串。

代码：

// 复用上面的 build_sa() 和 build_lcp()
int main() {
    scanf("%s", S);
    N = strlen(S);
    build_sa();
    build_lcp();
    int ans = 0;
    for (int i = 1; i < N; i++)
        ans = max(ans, lcp[i]);                      // ① LCP 最大值
    printf("%d\n", ans);
}

逐行解析：

• ① SA 中相邻两个后缀的 LCP 就是它们共享的最长子串。所有 LCP 的最大值就是答案。

---

例题 3：最长公共子串（两个字符串）

场景：两个字符串 $S$ 和 $T$，求最长公共子串长度。

数据范围：$1 \le |S|, |T| \le 10^5$

分析：把 $S$ 和 $T$ 拼成 $S$ + ’#’ + $T$（’#’ 是分隔符），对拼接串建 SA 和 LCP。答案 = 最大的 $LCP[k]$，其中 $SA[k]$ 和 $SA[k-1]$ 分别来自 $S$ 和 $T$。

代码：

char combined[200009];
int origin[200009]; // 0 = 来自 S, 1 = 来自 T

int main() {
    scanf("%s%s", S, T);
    int NS = strlen(S), NT = strlen(T);
    // ① 拼接
    for (int i = 0; i < NS; i++) { combined[i] = S[i]; origin[i] = 0; }
    combined[NS] = '#'; origin[NS] = 2;
    for (int i = 0; i < NT; i++) { combined[NS+1+i] = T[i]; origin[NS+1+i] = 1; }
    N = NS + 1 + NT;
    strcpy(S, combined); // 复用 build_sa

    build_sa();
    build_lcp();

    int ans = 0;
    for (int i = 1; i < N; i++)
        if (origin[sa[i]] != origin[sa[i-1]] &&     // ② 来自不同串
            origin[sa[i]] != 2 && origin[sa[i-1]] != 2) // ③ 不是分隔符
            ans = max(ans, lcp[i]);
    printf("%d\n", ans);
}

逐行解析：

• ① 拼接时用特殊字符分隔，保证跨串的 LCP 不会越过边界。
• ② 只有来自不同原始串的相邻后缀才对答案有贡献。
• ③ 排除分隔符位置。

---

例题 4：模式串出现次数

场景：文本串 $T$ 和模式串 $P$。求 $P$ 在 $T$ 中作为子串出现的次数。

数据范围：$1 \le |T| \le 10^5$，$1 \le |P| \le 10^5$

分析：$P$ 的所有出现位置对应 SA 中一段连续区间（因为字典序相邻）。用二分搜索找 $P$ 在 SA 中的上下界。

代码：

// 复用 build_sa()
// 比较 P 和后缀 sa[mid] 的前 |P| 个字符
int compare_suffix(int mid, const char* P) {
    int M = strlen(P);
    for (int i = 0; i < M; i++) {
        if (sa[mid] + i >= N) return -1;             // ① 后缀不够长
        if (S[sa[mid]+i] < P[i]) return -1;
        if (S[sa[mid]+i] > P[i]) return 1;
    }
    return 0;                                        // ② 匹配
}

int main() {
    char P[100009];
    scanf("%s%s", S, P);
    N = strlen(S);
    build_sa();
    int M = strlen(P);
    // ③ 二分找下界
    int lo = 0, hi = N;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (compare_suffix(mid, P) < 0) lo = mid + 1;
        else hi = mid;
    }
    int lb = lo;
    // ④ 二分找上界
    lo = 0; hi = N;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (compare_suffix(mid, P) <= 0) lo = mid + 1;
        else hi = mid;
    }
    printf("%d\n", lo - lb);                          // ⑤ 区间长度 = 出现次数
}

逐行解析：

• ① 如果后缀长度 < |P|，后缀比 P 小（因为后缀是 P 的前缀的子串）。
• ② 逐字符比较，确定大小关系。
• ③④ 两次二分搜索，找 SA 中 $P$ 的出现区间。
• ⑤ 上界 - 下界 = 出现次数。

参考文献

拓展练习 — AtCoder Library Practice Contest

• I Number of Substrings（不同子串计数 SA+LCP）【例题】

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化