后缀数组（SA）

参考资料

• 后缀数组（SA） - OI Wiki

简介

后缀数组（Suffix Array，SA）把字符串的所有后缀按字典序排序，$sa_i$ 为排名第 $i$ 的后缀起点，$rk$ 为其逆。常用倍增法 $O(n\log n)$ 构建，也有 SA-IS 等 $O(n)$ 做法。

配合 height 数组（排名相邻两后缀的最长公共前缀），后缀数组能解决本质不同子串数、可重叠/不可重叠最长重复子串等一类子串问题。

例题

洛谷 P3809 【模板】后缀排序

给定一个长度为 $n$ 的字符串，求其后缀数组，即把所有后缀按字典序升序排序后，各后缀的起始下标。