核心概述
后缀数组以字典序对所有后缀排序并配合 LCP/RMQ 支持多种子串查询，常用倍增法构建 O(n log n)、查询 LCP O(1)。
原文引述
Description: Suffix array SA and LCP array. Build O(n log n) (doubling + counting sort) or O(n) (SA-IS). Supports O(log n) LCP queries via RMQ over LCP array. Time: Build O(n log n); LCP query O(1) with sparse table (O(n log n) preprocessing) Status: tested ——摘自本节点现有英文注释
展开阐述
-
定义与背景、典型适用场景
- SA：将字符串所有后缀排序后的起点数组；配合 LCP 实现后缀比较、模式匹配、最长重复子串等。
- 适用于静态场景的全局子串关系分析；与自动机相比实现简洁。
-
接口/字段/数据结构与输入输出语义（按仓库约定）
- 结构：
- SA：vector
SA，SA[i] 为第 i 小后缀的起始位置。 - LCP：vector
LCP，LCP[i] 为 SA[i] 与 SA[i−1] 的最长公共前缀长度（LCP[0] 未定义）。 - 可选 RMQ：在 LCP 上构建稀疏表（见 011-数据结构-区间最值查询）以 O(1) 查询区间最小值。
- SA：vector
- 输出语义：
- SA 为 0-index 的长度 n 排列；LCP 长度 n，LCP[0]=0。
- 结构：
-
核心流程与关键要点
- 构造方法（倍增 + 基数排序）：
- 初始按单字符排序得到 SA、rank；
- 每轮按 (rank[i], rank[i+k]) 排序更新 SA；
- rank 唯一时结束。时间 O(n log n)。
- LCP（Kasai）：
- 线性时间根据 SA 计算相邻后缀 LCP，利用上一次比较长度 h 递减复用。
- 查询示例：
- 后缀比较：由 SA 位置直接给出。
- LCP(i,j)：将 i、j 的秩转为 SA 位置后，对 LCP 区间做 RMQ。
- 模式匹配：在 SA 上二分定位 p 的匹配区间，O(|p| log n)。
- 构造方法（倍增 + 基数排序）：
-
复杂度与边界条件
- 构建：O(n log n)（倍增）或 O(n)（SA-IS）。
- LCP：O(n)；单次 LCP 查询 O(1)（需 RMQ 预处理 O(n log n)）。
- 边界：空串/重复字符退化时的稳定性；字符集需全序比较并一致映射。
-
与相邻技术的取舍对比
- 与 125-字符串-后缀树：后缀自动机/树适合动态/多次查询；SA 更适合静态分析与实现简洁。
- 与模式匹配类：若仅单模式查找可用 121-字符串-KMP；回文等特殊结构可见 126-字符串-Z函数。
- 与哈希：指纹等价判定参见 119-字符串-字符串哈希，概率正确但实现更轻量。