前置约定与概念
- 本文字符串下标均从 (1) 开始.
- 对于原串 (S) , 记 (n) 为串长, 记 (Suf(i)) 表示 (S[i - n]) 这一子串.
- (SA) : (SA[i]) 表示后缀排序后排名第 (i) 的后缀的原串编号.
- (Rk) : (Rk[i]) 表示 (Suf(i)) 的排名.
- (LCP) : 最长公共前缀.
- (Height) : (Height[i]) 表示 (LCP (SA[i], SA[i - 1])) 的长度.
- "" 中的内容为字符或字符串, 小写字母为单个字符, 大写字母为字符串.
几个性质与结论
-
(SA[Rk[i]] = Rk[SA[i]] = i)
- 证明: 根据定义不难得出.
-
(LCP(Suf (i), Suf (j)) geq LCP(Suf (i), Suf (k)) (Rk[i] > Rk[j] > Rk[k]))
- 证明: 把 (LCP) 们放到 (Trie) 树上的叶子结点, 字典序相近的点表现为 (Trie) 树上 (LCA) 的深度更深, 即 (LCP) 越长.
-
(Height[Rk[i]] geq Height[Rk[i - 1]] - 1)
-
证明:
-
(Height[Rk[i - 1]] leq 1) 时, 成立.
-
考虑 (Height[Rk[i - 1]] > 1) 的情况.
令 (j = SA[Rk[i - 1] - 1]).
设 (Suf(i - 1)) 长这样: "aBC" (其中 B 长度为 (Height[Rk[i - 1]] - 1)), (Suf(j)) 长这样: "aBD".
因为 (Rk[j] < Rk[i - 1]) , 所以 "C" 的字典序大于"D".
又有: (Suf(i)) 长这样: "BC", (Suf(j + 1)) 长这样: "BD". 根据上一句话, 有(Rk[j + 1] < Rk[i]).
而又 (LCP (Suf (j + 1), Suf (i)) = B), 即 (|LCP (Suf (SA[Rk[i] - 1]), Suf (i))| geq |B| (结论2)).
上式等价于 (Height[Rk[i]] geq Height[Rk[i - 1]] - 1).
-
-
后缀排序过程详解
void SuffixSort() {
/*
SA[i]: 第一关键字排名第 i 的后缀的位置(编号).
Rk[i]: 第 i 位的后缀的第一关键字.
Rk1[i]: 第二关键字排名第 i 的后缀的第一关键字的位置(编号).
*/
m = 122;
// m 为第一关键字值域, 初始为字符集大小 ( ASCII 码值域 )
// 下面为(单关键字)基数排序
for (int i = 1; i <= n; ++i) ++Cnt[Rk[i] = S[i]];
// 这里 Cnt 数组存的是第一关键字值域, 相当于一个桶
for (int i = 2; i <= m; ++i) Cnt[i] += Cnt[i - 1];
/*
做一遍前缀和. 考虑此时 Cnt[i] 的意义, 实际上就是第一关键字 i 的排名.
说人话, 第一关键字为 i 的后缀们的排名区间是 [Cnt[i] - Size(i) + 1, Cnt[i]]
其中 Size(i) 指第一关键字为 i 的后缀数量.
*/
for (int i = n; i >= 1; --i) SA[Cnt[Rk[i]]--] = i;
/*
枚举后缀编号.
从内层分析, Rk[i] 用来获取 i 的第一关键字.
Cnt[Rk[i]] 用来定位第一关键字为 Rk[i] 的后缀的排名区间(右端点, 见上句代码的注释).
SA[Cnt[Rk[i]]] 确定排名为 Cnt[Rk[i]] 的后缀编号(即i).
Cnt[Rk[i]]-- 是缩小第一关键字为 i 的后缀们的排名区间, 防止同一位置有多个编号.
*/
for (int K = 1; K <= n; K <<= 1) { // 倍增
int Tot = 0; //只是一个单纯的计数器
for (int i = n - K + 1; i <= n; ++i) Rk1[++Tot] = i;
// 第一关键字位置在 [n - K + 1, n] 的后缀没有第二关键字, 把他们的第二关键字排名放到最前面.
for (int i = 1; i <= n; ++i) if (SA[i] > K) Rk1[++Tot] = SA[i] - K;
// 从小到大枚举排名, SA[i] > K 即其第一关键字能够作为其他后缀的第二关键字, 把其第一关键字扔到 Rk1 里面.
// 下面进行(双关键字)基数排序
for (int i = 1; i <= m; ++i) Cnt[i] = 0; // 清空 Cnt
for (int i = 1; i <= n; ++i) ++Cnt[Rk[i]];
for (int i = 2; i <= m; ++i) Cnt[i] += Cnt[i - 1];
/*
获取每一个第一关键字的排名区间: [Cnt[i] - Size(i) + 1, Cnt[i]]
其中 Size(i) 指第一关键字为 i 的后缀数量.
你可以这样去考虑: 因为第一关键字优先, 先确定第一关键字的绝对顺序, 再到每一个第一关键字相同的区间用第二关键字确定相对顺序.
*/
for (int i = n; i >= 1; --i) SA[Cnt[Rk[Rk1[i]]]--] = Rk1[i];
/*
从大到小枚举第二关键字排名.
Rk1[i] 定位其第一关键字位置, Rk[Rk1[i]] 获取第 Rk1[i] 位的第一关键字.
Cnt[Rk[Rk1[i]]] 获取 第一关键字为 Rk[Rk1[i]] 的排名区间.
Cnt[Rk[Rk1[i]]]--表示 Rk1[i] 占有这个坑位.
由于 Rk1[i] 在有着相同的第一关键字的后缀中第二关键字是最大的, 所以优先占有靠后的位置.
*/
std::swap (Rk, Rk1), Rk[SA[1]] = Tot = 1;
// 需要生成新的 Rk 数组, 但需要用到原来的, swap 一下
for (int i = 2; i <= n; ++i)
Rk[SA[i]] = (Rk1[SA[i]] == Rk1[SA[i - 1]] && Rk1[SA[i] + K] == Rk1[SA[i - 1] + K])? Tot : ++Tot; //去重的意思, 新的第一关键字相同当且仅当久的两个关键字都相同.
if (Tot == n) break; m = Tot;
// 如果 n 个后缀互不相同, 说明已排好序, 直接退出.
// m = Tot 用来获取新的第一关键字值域.
}
}