感谢 LB 学长的博文！
前置知识
后缀是指从某个位置 (i) 开始到整个串末尾结束的一个特殊子串，也就是 (S[i dots|S|-1])。
计数排序 – OI Wiki (oi-wiki.org)
基数排序 – OI Wiki (oi-wiki.org)
变量
后缀数组最主要的两个数组是 sa 和 rk。
sa 表示将所有后缀排序后第 (i) 小的后缀的编号，即编号数组。
rk 表示后缀 (i) 的排名，即排名数组。
这两个数组满足一个重要性质： sa[rk[i]] = rk[sa[i]] = i。
示例：
这个图很好理解。
做法
暴力的 (O_{n^2 log n}) 做法
将所有的后缀数组都 sort 一遍，sort 复杂度为 (O_{n log n})，字符串比较复杂度为 (O_{n})，总的复杂度 (O_{n^2 log n})。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include
using namespace std;
typedef long long ll;
template
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch ans[N];
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i 倍增优化的 (O_{n log^2 n}) 做法
先对长度为 (1) 的所有子串，即每个字符排序，得到排序后的 sa1 和 rk1 数组。
之后倍增：
-
用两个长度为 (1) 的子串的排名，即
rk1[i]和rk1[i + 1]，作为排序的第一关键词和第二关键词，这样就可以对每个长度为 (2) 的子串进行排序，得到sa2和rk2； -
之后用两个长度为 (2) 的子串的排名，即
rk2[i]和rk2[i + 2]，来作为排序的第一关键词和第二关键词。（为什么是 (i + 2) 呢，因为rk2[i]和rk2[i + 1]重复了 (S_{i + 1})）这样就可以对每个长度为 (4) 的子串进行排序，得到sa4和rk4； -
重复上面的操作，用两个长度为 (dfrac{w}{2}) 的子串的排名，即
rk[i]和rk[i + (w / 2)]，来作为排序的第一关键词和第二关键词，直到 (w ge n)，最终得到的sa数组就是我们的答案数组。
示意图：
倍增的复杂度为 (O_{log n})，sort 复杂度为 (O_{n log n})，总的复杂度 (O_{n log ^ 2 n})。
排序优化的 (O_{n log n}) 的做法
发现后缀数组值域即为 (n)，又是多关键字排序，考虑基数排序。
上面已经给出一个用于比较的式子：(A[i] ，倍增过程中 A[i], B[i] 大小关系已知，先将 B[i] 作为第二关键字排序，再将 A[i] 作为第一关键字排序，两次计数排序实现即可。
单次计数排序复杂度 (O_{n+w})（(w) 为值域，显然最大与 (n) 同阶），总时间复杂度变为 (O_{n log n})。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include
using namespace std;
typedef long long ll;
template
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch = 1; -- i) {
sa[cnt[rk[i]] --] = i;
}
memcpy(oldrk + 1, rk + 1, n * sizeof(int));
/*--------------------------------*/
// 判重
for (int cur = 0, i = 1; i = 1; -- i) {
sa[cnt[rk[oldsa[i] + w]] --] = oldsa[i];
}
/*--------------------------------*/
// 再按照第一关键词计数排序
memset(cnt, 0, sizeof cnt);
memcpy(oldsa + 1, sa + 1, n * sizeof(int));
for (int i = 1; i = 1; -- i) {
sa[cnt[rk[oldsa[i]]] --] = oldsa[i];
}
/*--------------------------------*/
// 更新数组
memcpy(oldrk + 1, rk + 1, n * sizeof(int));
for (int cur = 0, i = 1; i 各种常数优化
- 考虑我们按照第二关键词排序的实质，就是将超出 (n) 范围的空字符串放在
sa的最前面，在本次排序中，(S[sa_i dots sa_i+2^k−1]) 是长度为 (2^k) 的子串 (S[sai−2^k−1 dots sai+2^k−1]) 的后半截，sa[i]的排名将作为排序的关键字。
(S[sa_i,sa_i+2^k−1]) 的排名为 (i)，则第一次计排后 (S[sa_i−2^k−1 dots sa_i+2^k−1]) 的排名必为 (i)，考虑直接赋值。
for (p = 0, i = n; i > n - w; -- i) {
oldsa[++ p] = i;
}
for (int i = 1; i w) { // 保证 sa[i] 是后半截的编号
oldsa[++ p] = sa[i] - w; // sa[i] 一定是后半截的编号，而我们要存的是前半截的开始编号
}
}
-
减小值域，每次对
rk进行更新之后，我们都计算了一个 (p)，这个 (p) 即是rk的值域，将值域改成它即可。 -
将
rk[id[i]]存下来，减少不连续内存访问。 -
用函数
cmp来计算是否重复。 -
若排名都不相同可直接生成后缀数组。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include
using namespace std;
typedef long long ll;
template
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch = 1; -- i) {
sa[cnt[rk[i]] --] = i;
}
for (int w = 1; ; w n - w; -- i) {
oldsa[++ p] = i;
}
for (int i = 1; i w) { // 保证 sa[i] 是后半截的编号
oldsa[++ p] = sa[i] - w; // sa[i] 一定是后半截的编号，而我们要存的是前半截的开始编号
}
}
memset(cnt, 0, sizeof cnt);
for (i = 1; i = 1; -- i) {
sa[cnt[key[i]] --] = oldsa[i];
}
memcpy(oldrk + 1, rk + 1, n * sizeof(int));
for (p = 0, i = 1; i 参考资料
后缀数组简介 – OI Wiki (oi-wiki.org)
「笔记」后缀数组 – Luckyblock – 博客园 (cnblogs.com)
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
大家好！我是sum墨，一个一线的底层码农，平时喜欢研究和思考一些技术相关的问题并整理成文，限于本人水平，如果文章和代码有表述不当之处，还请不吝赐教。 以下是正文！ 先看问题 首先上一串代码 public String buy(Long goodsId, Int…
