在学校补了几天的动规,算是把一些基本题型都弄完了。
回来继续做 NOI 知识点~
不过可能过几天又要补 DP 了
引入
后缀数组(\(\text{Suffix Array}\),简称 \(\text{SA}\))通过利用各种算法进行后缀排序来维护数组,实现很多与后缀相关的问题。
模板
洛谷传送门
读入一个字符串,把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输出后缀的第一个字符在原串中的位置。
追问:完成以上操作后,输出排序后相邻两个非空后缀的最长公共前缀的长度。
解析:后缀数组的求法一共有四种:直接排序后暴力求解,时间复杂度为 \(O(n^2\log n)\);使用倍增法求解,时间复杂度为 \(O(n\log n)\);DC3 算法,时间复杂度为 \(O(n)\) 但常数较大;SA-IS 算法,时间复杂度为 \(O(n)\) 且常数更小。
其中,倍增法的效率、思维量和码量都比较适合竞赛中使用,所以这里重点讲倍增法。如果想了解 DC3 和 SA-IS 算法,文末会放上几篇相关文章的链接。
后缀数组需要维护以下几个数组:
- \(sa_i\),表示将所有后缀排序后第 \(i\) 小的后缀的编号;
- \(rk_i\),表示第 \(i\) 个后缀的排名;
- \(height_i\),表示 \(sa_i\) 与 \(sa_{i-1}\) 的最长公共前缀。
实际上, \(sa_i\) 和 \(height_{i}\) 就是我们要求的东西,而 \(rk_i\) 与 \(sa_i\) 对偶。
求 \(sa_i\)
- 我们先把第一个字符作为第一关键字排序;若第一关键字相同,则保持相对位置不变。这个过程可以用基数排序做到 \(O(n)\) 的时间复杂度。
- 接下来进行倍增。假设进行了 \(k\) 轮排序,前 \(k\) 个字符都已经按照字典顺序排序好。那么,我们把前 \(k\) 个字符作为第一关键字, \(k+1\sim 2k\) 的字符作为第二关键字排序。每一轮操作结束后将前 \(k\) 个字符进行离散化得到一个整数,\(k+1\sim 2k\) 同理。
这样每次排序后 \(k\) 都会扩大 \(2\) 倍,因此最多只会进行 \(O(\log n)\) 次排序,总时间复杂度为 \(O(n\log n)\)。
求 \(height_i\)
假设我们已经完成了求 \(sa_i\) 的操作。记 \(rk_i\) 和 \(rk_j\) 的后缀的最长公共前缀长度为 \(lcp(i,j)\),则有以下性质:
- \(lcp(i,j)=lcp(j,i)\);
- \(lcp(i,i)=\text{strlen}(i)\);
- \(\forall k\in [i,j],\; lcp(i,j)=\min\{lcp(i,k),lcp(k,j)\}\)。
利用以上几个性质,我们就可以把 \(lcp(i,j)\) 转化为循环求相邻两个数组的 \(lcp\)。显然, \(height_i=lcp(i-1,i)\)。
可以证明:\(\forall i\in[1,n],\; height_{rk_i}\geq height_{rk_{i-1}}-1\)。据此,我们可以通过维护一个指针在 \(O(n)\) 的时间复杂度中完成 \(height_i\) 的求解。
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 1e6 + 10;
int n, m = 122; // m 为基数排序的值域
char s[maxn];
class Suffix_Array {
private:
int x[maxn], y[maxn], c[maxn]; //一号关键字,二号关键字,每个关键字的个数
public:
int sa[maxn], rk[maxn], height[maxn];
void get_sa() {
for (int i = 1; i <= n; i++) c[x[i] = s[i]]++;
for (int i = 2; i <= m; i++) c[i] += c[i - 1];
for (int i = n; i > 0; i--) sa[c[x[i]]--] = i; //基数排序部分
for (int k = 1; k <= n; k <<= 1) {
int p = 0;
for (int i = n - k + 1; i <= n; i++) y[++p] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > k) y[++p] = sa[i] - k;
for (int i = 1; i <= m; i++) c[i] = 0;
for (int i = 1; i <= n; i++) c[x[i]]++;
for (int i = 2; i <= m; i++) c[i] += c[i - 1];
for (int i = n; i; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
swap(x, y);
x[sa[1]] = 1, p = 1;
for (int i = 2; i <= n; i++)
if (y[sa[i]] == y[sa[i - 1]] &&
y[sa[i] + k] == y[sa[i - 1] + k])
x[sa[i]] = p;
else
x[sa[i]] = ++p;
if (p == n) break;
m = p; //更新基数排序值域
}
}
void get_height() {
for (int i = 1; i <= n; i++) rk[sa[i]] = i;
for (int i = 1, k = 0; i <= n; i++) {
if (rk[i] == 1) continue;
if (k) k--;
while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
height[rk[i]] = k;
}
}
} SA;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> (s + 1);
n = strlen(s + 1);
SA.get_sa(), SA.get_height();
for (int i = 1; i <= n; i++) cout << SA.sa[i] << ' ';
cout << '\n';
for (int i = 1; i <= n; i++) cout << SA.height[i] << ' ';
return 0;
}
例题讲解
后缀数组的例题有很多,且有的可以用后缀自动机等其它字符串算法解决,所以只放几个典型题目。
[NOI2015] 品酒大会
洛谷传送门
给定一个字符串,每个字符都有一个权值 \(a_i\)。若字符 \(p\) 与字符 \(q\) 的后缀 \(P,Q\) 满足 \(lcp(P,Q)\geq r\),则称这两个字符满足 “\(r\) 相似”。求出对于 \(r=0,1,2,...,n-1\) 时使满足 \(r\) 相似的配对个数,并对于 \(r\) 的每个取值,求出 \(p\) 和 \(q\) 满足 \(r\) 相似时 \(a_p\times a_q\) 的最大值。
解析:先对字符串做一个后缀排序。
对于第一问,我们可以给每一个 \(r\) 找到一个 \(height_i<r\),那么可以找到 \(height_i<r\) 的分界线把所有后缀分成两组,组内两两配对都可以做到 \(r\) 相似,且组外都一定不存在 \(r\) 相似的字符,这样就可以直接统计了。
对于第二问,进行分类讨论:
- \(a_p,a_q>0\),找到最大值和次大值相乘;
- \(a_p,a_q<0\),找到最小值和次小值相乘;
- \(a_q<0,a_p>0\)。处于这种情况时一定是只有这两个取值可用(否则可以转化成前两种情况,得到结果一定会更优),也可以看成求最大和次大值。
由于 \(r\) 的每个取值都要求出一个答案,所以我们考虑 \(r\) 的遍历顺序。如果正向遍历,字符串将会由于分界线从整到散,这不利于求出第二问。所以我们逆向枚举,这样字符串就从零化整(同时利用了所有 \(r\) 相似都满足 \(r-1\) 相似),容易维护答案了。
我们维护每个段的长度 \(size\),最大、次大值 \(max_1,max_2\),最小、次小值 \(min_1,min_2\)。那么合并两个段时只需要比较两个段的各个数据,并做一些简单的分类讨论就可以得到新段。为了更方便地维护合并和查询的操作,使用并查集。
inline ll get(int x) { return x * (x - 1LL) / 2; }
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
auto solve(int r) {
for (auto x : hs[r]) {
int a = find(x - 1), b = find(x); //对每个相邻段求解
cnt -= get(sz[a]) + get(sz[b]);
fa[a] = b, sz[b] += sz[a];
cnt += get(sz[b]);
if (max1[a] >= max1[b]) { //最大值更大,更新并判断次大值
max2[b] = max(max1[b], max2[a]);
max1[b] = max1[a];
} else if (max1[a] > max2[b]) //最大值不变但次大值更大
max2[b] = max1[a];
if (min1[a] <= min1[b]) { //最小值和次小值同理
min2[b] = min(min1[b], min2[a]);
min1[b] = min1[a];
} else if (min1[a] < min2[b])
min2[b] = min1[a];
res = max(res, max(max1[b] * max2[b], min1[b] * min2[b]));
}
if (res == -inf) //res 初始化为负无穷,没有更新时返回 0
return make_pair(cnt, (long long)0);
else
return make_pair(cnt, res);
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
cin >> (s + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
SA.get_sa(), SA.get_height();
for (int i = 2; i <= n; i++) hs[SA.height[i]].push_back(i); //记录所有 r 相似的取值
for (int i = 1; i <= n; i++) { //初始化并查集
fa[i] = i, sz[i] = 1;
max1[i] = min1[i] = a[SA.sa[i]];
max2[i] = -inf, min2[i] = inf;
}
for (int i = n - 1; i >= 0; i--) ans[i] = solve(i);
for (int i = 0; i < n; i++)
cout << ans[i].first << ' ' << ans[i].second << '\n';
return 0;
}
不同子串个数
洛谷传送门。
给定一个字符串,求出该串本质不同的子串个数。
解析:先确定枚举的起点,那么要枚举其实就是起点对应后缀的所有前缀。即,所有后缀的前缀集合 \(=\) 所有子串集合。这样就可以利用后缀数组排序,求出 \(height_i\) 数组,并得到答案为所有字串长度之和减去它们的 \(height_i\) 之和。
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> (s + 1);
SA.get_sa(), SA.get_height();
long long ans = 1LL * n * (n + 1) / 2; //所有子串长度和为 n * (n + 1) / 2
for (int i = 1; i <= n; i++) ans -= SA.height[SA.rk[i]];
cout << ans;
return 0;
}
这道题很简单,放进来的目的在于引出下面这题。
[SDOI2016]生成魔咒
洛谷传送门
给定一个字符串(其实是一个序列),对每个前缀求出本质不同的子串个数。
解析:还是先考虑求解的方向。显然如果模拟题意从前往后计算,那么 \(height_i\) 数组难以求出。所以我们把字符串翻转一下,对每个后缀求本质不同的子串个数。这样我们的任务就转化为动态维护 \(height_i\) 数组,求出对应的贡献即可。
在实现上,由于序列的值域很大,所以要先做一遍离散化;此外完成贡献的子串不能重复计数,所以要做一个“删除”操作。可以用平衡树或者 set,由于不需要多么高深的查询操作,所以维护一个双向链表就够了。
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = n, x; i; i--) { //边输入边离散化,顺便翻转序列
cin >> x;
if (!Hash[x]) Hash[x] = ++m;
s[i] = Hash[x];
}
SA.get_sa(), SA.get_height();
for (int i = 1; i <= n; i++) { //预处理双向链表
tmp += n - SA.sa[i] + 1 - SA.height[i];
u[i] = i - 1, d[i] = i + 1;
}
d[0] = 1, u[n + 1] = n;
for (int i = 1; i <= n; i++) {
ans[i] = tmp;
int k = SA.rk[i], j = d[k];
tmp -= n - SA.sa[k] + 1 - SA.height[k];
tmp -= n - SA.sa[j] + 1 - SA.height[j];
SA.height[j] = min(SA.height[j], SA.height[k]); //维护删除后的 height 数组
tmp += n - SA.sa[j] + 1 - SA.height[j];
d[u[k]] = d[k], u[d[k]] = u[k]; // 在链表上删除
}
for (int i = n; i; i--) cout << ans[i] << '\n';
return 0;
}
标签:lcp,get,后缀,Coel,笔记,height,int,sa
From: https://www.cnblogs.com/Coel-Flannette/p/16610423.html