后缀数组
stripe_python
·
2026-07-07 19:54:00
·
算法·理论
定义
全文使用 1-index。
对于字符串 S ,定义 \text{sa}[i] 为将 S 排序后第 i 小后缀的标号,\text{rk}[i] 为标号为 i 的后缀排序。根据定义,\text{sa} 和 \text{rk} 互为逆排列。
记 \text{lcp}(i,j) 为 S[i:n] 和 S[j:n] 的 LCP 长度,设 \text{ht}[i]=\text{lcp}(\text{sa}[i-1],\text{sa}[i]) 。
求法
哈希
初始化 \text{sa} 为单位排列,对其进行排序。每轮 cmp 只要比较两个后缀的字典序,二分哈希求 LCP 长后比较下一位即可。
复杂度为 O(n \log^2 n) 。建议使用倍增求 LCP 配合 std::stable_sort。
倍增
考虑在第 k 轮排序中只比较 S[i:i+2^k-1] 的字典序。
在第 k+1 轮中,我们需要对 (S[i:i+2^k-1], S[i+2^k:i+2^{k+1}-1]) 的二元组排序。这两个东西在上一轮都排好了,所以可以直接 std::sort。复杂度 O(n \log^2 n) 。
由于值域是 O(n) 的,可以用计数排序来优化。对于双关键字排序,还要采用基数排序的思想,先对第二关键字排序,再对第一关键字排序。复杂度 O(n \log n) 。
常数优化:第二关键字排序可以直接模拟;限制值域。
板子
倍增实现的单 \log 做法。
struct suffix_array {
int sa[2 * N], rk[2 * N], ht[N], rk0[N], cnt[N], id[N];
void init(const char* s, int n, int m = 130) {
for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
for (int k = 1, p = 0; p < n; k <<= 1, m = p) {
int cur = 0;
for (int i = n-k+1; i <= n; i++) id[++cur] = i;
for (int i = 1; i <= n; i++) if (sa[i] > k) id[++cur] = sa[i] - k;
fill(cnt + 1, cnt + m + 1, 0);
for (int i = 1; i <= n; i++) cnt[rk[id[i]]]++;
for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i];
p = 0, copy(rk + 1, rk + n + 1, rk0 + 1);
auto equ = [&](int x, int y) -> bool {
return rk0[x] == rk0[y] && rk0[x + k] == rk0[y + k];
};
for (int i = 1; i <= n; i++) rk[sa[i]] = equ(sa[i - 1], sa[i]) ? p : ++p;
}
for (int i = 1, j = 0; i <= n; i++) {
if (rk[i] == 0) continue;
for (j ? j-- : 0; s[i+j] == s[sa[rk[i]-1] + j]; ) j++;
ht[rk[i]] = j;
}
}
} SA;
结论
- 我们常常会对 $\text{ht}$ 建小根笛卡尔树。这个结构的本质是后缀树。
本质不同子串数 \dbinom{n}{2}-\sum\limits_{i=2}^n \text{ht}[i] 。
练习
P4248 [AHOI2013] 差异
给出长为 n 的字符串 S ,记 T_i=S[i:n] ,求
\sum_{1 \le i< j \le n} (|T_i|+|T_j|-2 \times \text{lcp}(T_i,T_j))
:::::success[题解]
前面 \sum\limits_{1 \le i<j \le n} (|T_i|+|T_j|) 容易推式子变成 \frac{n(n-1)(n+1)}{2} 从而 O(1) 计算。
求出 \text{ht} 数组后,相当于我们要对区间 \min 求和。这是 AGC005B,做法是单调栈求出以 \text{ht}[x] 为 \min 的极长区间,算一下贡献。
注意单调栈一侧取等一侧不取的细节。
:::::
:::::info[代码]
void _main() {
cin >> (s + 1); n = strlen(s + 1);
SA.init(s, n);
i64 res = 1LL * (n - 1) * n * (n + 1) / 2;
stack<int> st;
for (int i = 2; i <= n; i++) {
while (!st.empty() && SA.ht[st.top()] > SA.ht[i]) st.pop();
l[i] = st.empty() ? 2 : st.top() + 1; st.emplace(i);
}
while (!st.empty()) st.pop();
for (int i = n; i >= 2; i--) {
while (!st.empty() && SA.ht[st.top()] >= SA.ht[i]) st.pop();
r[i] = st.empty() ? n : st.top() - 1; st.emplace(i);
}
for (int i = 2; i <= n; i++)
res -= 2LL * (i - l[i] + 1) * (r[i] - i + 1) * SA.ht[i];
cout << res;
}
:::::
P6640 [BJOI2020] 封印
给定字符串 S,T ,字符集为 \{\tt{a},\tt{b}\} 。q 次询问给定 l,r ,求 S[l:r] 与 T 的最长公共子串长度。
:::::success[题解]
钦定 i 为 S 中子串的起始位置,求出最长公共子串长度,记为 f_i 。枚举最长公共子串的起点 i ,则询问 [l,r] 的答案为
\max_{i \in [l,r]} \min(f_i,r-i+1)
二分答案 k ,则 \exists i \in [l,r], \min(f_i,r-i+1) \ge k 。拆开不等式得 f_i \ge k \land r-i+1 \ge k ,转化为 \max\limits_{i \in [l,r-k+1]} f_i \ge k 。用 ST 表维护,复杂度 1log。
:::::
:::::info[代码]
```cpp line-numbers
const int N = 4e5 + 5, inf = 1e9;
int n, m, q, f[N], st[20][N];
string s, t;
int ask(int l, int r) {
int k = lg(r - l + 1);
return max(st[k][l], st[k][r - (1 << k) + 1]);
}
void _main() {
cin >> s >> t; n = s.size();
string a = ' ' + s + '#' + t;
m = a.size() - 1, SA.init(a.c_str(), m);
for (int i = 1, k = 0; i <= m; i++) {
chkmin(k, SA.ht[i]);
if (SA.sa[i] > n + 1) k = inf;
if (SA.sa[i] <= n) chkmax(f[SA.sa[i]], k);
}
for (int i = m, k = 0; i >= 1; i--) {
if (SA.sa[i] > n + 1) k = inf;
if (SA.sa[i] <= n) chkmax(f[SA.sa[i]], k);
chkmin(k, SA.ht[i]);
}
copy(f + 1, f + n + 1, st[0] + 1);
for (int i = 1; (1 << i) <= n; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
cin >> q;
for (int l, r; q--; ) {
cin >> l >> r;
int lo = 1, hi = r - l + 1, res = 0;
while (lo <= hi) {
int k = (lo + hi) >> 1;
if (ask(l, r - k + 1) >= k) res = k, lo = k + 1;
else hi = k - 1;
}
cout << res << '\n';
}
}
```
:::::
### [P4770 [NOI2018] 你的名字](https://www.luogu.com.cn/problem/P4770)
> 给定字符串 $S$,$q$ 次询问给出 $l,r,T$,求 $T$ 中不在 $S[l:r]$ 内出现的本质不同子串数。
>
> $|S| \le 5 \times 10^5$,$q \le 10^5$,$\sum |T| \le 10^6$,5 秒,1024 MB。
### [P6793 [SNOI2020] 字符串](https://www.luogu.com.cn/problem/P6793)
> 给定两个长为 $n$ 的字符串 $A,B$ 和正整数 $k$。各自取出所有长为 $k$ 的子串组成集合 $S,T$。
>
> 你需要将 $S$ 和 $T$ 中的元素两两匹配,匹配 $s,t$ 的代价为 $k-\text{lcp}(s,t)$。最小化代价并输出。
>
> $k \le n \le 1.5 \times 10^5$,1 秒,256 MB。
:::::success[题解]
不妨视匹配 $s,t$ 的权值为 $\text{lcp}(s,t)$,转为最大权完美匹配。
对 $A{\tt{\#}}B$ 后缀排序得到 $\text{ht}$ 数组,权值可以描述为 $\text{ht}$ 数组的区间 $\min$。由于区间 $\min$ 满足四边形不等式,或者说相交劣于包含的性质,我们可以直接贪心匹配权值最小的边。
考虑维护贪心过程。对 $\text{ht}$ 建小根笛卡尔树,自底向上贪心。对节点 $u$,我们维护失配的 $s,t$ 数目 $x,y$,并在 $u$ 处尽可能匹配。
形式化地,我们求出 $q=\min(x,y)$,对答案累加 $q \times \min(k,\text{ht}[u])$ 后,将 $x \gets x-q, y \gets y-q$ 传递给父亲进行匹配即可。
线性 SA 可以做到总复杂度线性。
:::::
:::::info[代码]
```cpp line-numbers
const int N = 3e5 + 5;
int n, k, m, l[N], r[N];
string a, b;
int build(int* a) {
int rt = -1; stack<int> st;
for (int i = 2; i <= m; i++) {
while (!st.empty() && a[st.top()] > a[i]) l[i] = st.top(), st.pop();
st.empty() ? (rt = i) : (r[st.top()] = i), st.emplace(i);
} return rt;
}
i64 ans;
pair<int, int> dfs(int u) {
int x = 0, y = 0;
if (l[u]) {
auto [x0, y0] = dfs(l[u]);
x += x0, y += y0;
} else {
int v = SA.sa[u-1];
x += (v <= n-k+1), y += (n+2 <= v && v <= 2*n-k+2);
}
if (r[u]) {
auto [x0, y0] = dfs(r[u]);
x += x0, y += y0;
} else {
int v = SA.sa[u];
x += (v <= n-k+1), y += (n+2 <= v && v <= 2*n-k+2);
}
i64 q = min(x, y); ans += q * min(k, SA.ht[u]);
return {x - q, y - q};
}
void _main() {
cin >> n >> k >> a >> b;
string c = ' ' + a + '#' + b;
m = c.size() - 1, SA.init(c.c_str(), m);
int rt = build(SA.ht); dfs(rt);
cout << 1LL * k * (n - k + 1) - ans;
}
```
:::::