后缀数组

· · 算法·理论

后缀数组

后缀数组（Suffix Array），主要关系到两个数组 sa 和 rk。sa_i 表示将所有后缀排序后第 i 小的后缀的编号，rk 表示后缀 i 的排名。

显然，rk_{sa_i}=sa_{rk_i}=i。

O(n\log^2{n}) 求法

  1. 对所有长为 1 的子串排序

  2. 对所有长为 2 的子串排序（以 rk_i 为第一关键字，rk_{i+1} 为第二关键字）

  3. 对所有长为 4 的子串排序（以 rk_i 为第一关键字，rk_{i+2} 为第二关键字）

  4. 以此类推

如果每次 sort，总时间复杂度 O(n\log^2{n})。

O(n\log{n}) 求法

考虑用基数排序优化 sort。即按照先排第二关键字确定初步的相对顺序，再根据第一关键字排序。（内部用桶排）

Height

**结论 1：**$height_{rk_i}\geq height_{rk_{i-1}}-1

证明：

设后缀 i-1 是 sAC，pre(i-1) 是 sAB，且 height_{rk_{i-1}}= len(sA)。

则后缀 i 是 AC。

实际 AB\leq pre(i)< AC，所以 height_{rk_i}\leq len(A)=height_{rk{i-1}}-1。

通过结论 1 可以 O(n) 求 height。

for (int i = 1, j = 0; i <= n; i ++) {
    if (j) j --;
    while (sa[rk[i]] + j <= n && sa[rk[i] - 1] + j <= n && s[sa[rk[i]] + j] == s[sa[rk[i] - 1] + j]) j ++;
    height[rk[i]] = j;
}

结论2：lcp(sa_i,sa_j)=\min{height_{i+1,i+2\cdot\cdot\cdot j}}

应用

子串就是后缀的前缀，所以可以枚举每个后缀，计算重复的前缀总数，用总方案减掉重复的方案。

所以答案应为：\frac{n\times (n+1)}{2}-\sum_{i=2}^n{height_i}。

[SDOI2016] 生成魔咒

对每个前缀求，本质不同的子串数。

考虑在字符串末尾插入一个新字符，最多会有 O(n) 个 height 被更改。

若是在字符串首部插入一个字符，最多只有包括前驱、后继的 O(1) 个 height 被更改。所以可以把字符串倒过来处理。

每次加入一个字符，可以获得一个新的后缀，它的排名是 rk_i。维护 set，找到当前排名的前驱后继，重新计算他们的 height。

[USACO06DEC] Milk Patterns G

求出 height 序列，然后以长度为 k-1 进行滑动窗口，维护滑窗的最小的最大即为答案。

[TJOI2019] 甲苯先生和大中锋的字符串

要求出现次数恰好为 k，还是以长度为 k-1 进行滑动窗口，注意当滑窗两端的 height 都小于当前滑窗最小值时才统计答案。

[SDOI2008] Sandy 的卡片

先把所有串中间加一个分隔符连起来。

二分答案 mid，只去 height>=mid 的部分，若有一个极长连续段包含了每个串的元素作为后缀的开头，则满足条件。

优秀的拆分

考虑如何统计形如 AA 的串的数量。

枚举 len(A)，把所有 len 的倍数的点叫做特殊点，那么 AA 应该恰好覆盖两个特殊点。

考虑两个相邻特殊点 i 和 j 对答案的贡献。

令 lcp=lcp(i,j)，lcs=lcs(i-1,j-1)。（lcp(i,j) 表示后缀 i 和后缀 j 的 lcp，lcs(i,j) 表示前缀 i 和前缀 j 的 lcs）

那么如图那一段黄色都可以表示为 AA。