首页 技术 正文
技术 2022年11月23日
0 收藏 618 点赞 2,552 浏览 5950 个字

知识点: 广义 SAM

原题面 Luogu


「扯」

随便「口胡」一下居然「过」了。

比较考验「代码能力」,第一次感觉「大模拟」没有白写(((

还有这个「符号」实在是太「上头」了。


前置知识

在线构造广义 SAM,推荐:【学习笔记】字符串—广义后缀自动机 – 辰星凌


题意简述

给定 \(n\) 个仅包含小写字母的字符串 \(S_1\sim S_n\)。

定义字符串 \(S_i\) 的 「独特值」为只属于该串的本质不同的非空子串的个数。

求字符串 \(S_1\sim S_n\) 的「独特值」。

\(1\le n\le 10^5, 1\le \sum|S_i|\le 10^5\)。


分析题意

算法一

多串子串问题,考虑广义 SAM。

若 \(n\) 较小,直接维护每个状态 包含几个串的信息。

parent 树上 DP 更新祖先信息,直接更新答案即可。

但 \(n\le 10^5\) 空间爆炸,做不得,考虑乱搞一波。


算法二

用 string 存字符串,建广义 SAM。

在动态建立 SAM 时,\(\operatorname{only}_i\) 记录每个状态 \(i\) 包含哪一个串的信息。

若某状态包含多个串信息,则\(\operatorname{only}_i = – 1\)。

parent 树上 DP 更新祖先信息。

先考虑一波 无脑暴力:

对于 \(S_i\),枚举其所有子串,在 SAM 上跑出对应状态 \(u\)。

若有 \(\operatorname{only}_u\not = -1\), 对应状态只维护了一个串的信息,一定为该子串。

这样的子串数,即为 \(S_i\) 的「独特值」。


上述算法瓶颈是枚举子串。发现前缀有一些好性质:

  1. 连续前缀 对应状态在 SAM 上也是连续的,实现时直接把串扔到 SAM 上跑 即得对应状态。
  2. 前缀对应状态到 parent 树根的链上 包含该前缀所有后缀,可以包含所有子串信息。

考虑仅枚举前缀,枚举复杂度变为线性。


发现一些结论:

  1. parent 树上一条从叶到根的链,维护的串的个数,是单调不减的。
  2. 若某状态 \(i\) 的 \(\operatorname{only}_i\not = -1\), 则对于其子树中所有状态 \(j\),有 \(\operatorname{only}_j=\operatorname{only}_i\)。

考虑维护状态 \(i\) 的 parent 树上距它最远的,\(\operatorname{only}\not= -1\) 的祖先 \(\operatorname{top}_i\)。

由结论 1,若某状态 \(i\) 的 \(\operatorname{only}_i=-1\),\(\operatorname{top}_i=0\)。

由结论 2,跑到的 \(\operatorname{only}\not= – 1\) 的节点对答案有贡献,在其子树中所有节点都会有贡献。

可预处理子树 \(\operatorname{len}(i)-\operatorname{len}(\operatorname{link}(i))\) 之和 \(\operatorname{sum}\),即某子树中的子串数量。

统计答案时,统计 跑到的状态 \(u\) 的 \(\operatorname{sum}(\operatorname{top}_u)\),一个 \(\operatorname{top}_u\) 只能统计一次,去重可用排序实现。

这样为什么是对的?考虑前缀的性质 2 感性理解一下。

每个串都在 SAM 上进行一匹配 并进行一次排序,总复杂度大概是 \(O(\sum\limits_{i}^{n} |S_i|\log |S_i|)\),可过。


算法三

瞅了一眼题解,发现自己做麻烦了。

DP 求得 \(\operatorname{only}\) 后,直接遍历所有状态,若存在 \(\operatorname{only}_i \not= -1\),则令 \(ans _{\operatorname{only}_i}\) 加上 \(\operatorname{len}(i)-\operatorname{len}(\operatorname{link}(i))\)即可。

复杂度 \(O(\sum|S_i|)\),少一个排序的复杂度。


爆零小技巧

前缀和 没有加 前缀的和。

你的前缀和既不前,也不缀,更不和。


代码实现

算法三

//知识点:SAM
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define ll long long
const int kMaxn = 2e5 + 10;
const int kMaxm = 26;
//=============================================================
std :: string S[kMaxn];
int only[kMaxn << 1], ans[kMaxn];
int num, node_num = 1, ch[kMaxn << 1][kMaxm], len[kMaxn <<1], link[kMaxn << 1];
int edge_num, head[kMaxn], v[kMaxn << 1], ne[kMaxn << 1];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void AddEdge(int u_, int v_) {
v[++ edge_num] = v_, ne[edge_num] = head[u_], head[u_] = edge_num;
}
int Insert(int c_, int last_) {
if (ch[last_][c_]) {
int p = last_, q = ch[p][c_];
if (len[p] + 1 == len[q]) {
only[q] = - 1;
return q;
}
int newq = ++ node_num;
memcpy(ch[newq], ch[q], sizeof(ch[q]));
len[newq] = len[p] + 1;
link[newq] = link[q];
link[q] = newq;
for (; p && ch[p][c_] == q; p = link[p]) ch[p][c_] = newq;
only[newq] = num;
return newq;
}
int p = last_, now = ++ node_num;
only[now] = num;
len[now] = len[p] + 1;
for (; p && ! ch[p][c_]; p = link[p]) ch[p][c_] = now;
if (! p) {link[now] = 1; return now;}
int q = ch[p][c_];
if (len[q] == len[p] + 1) {link[now] = q; return now;}
int newq = ++ node_num;
memcpy(ch[newq], ch[q], sizeof(ch[q]));
link[newq] = link[q], len[newq] = len[p] + 1;
link[q] = link[now] = newq;
for (; p && ch[p][c_] == q; p = link[p]) ch[p][c_] = newq;
return now;
}
void Dfs1(int u_) {
for (int i = head[u_]; i; i = ne[i]) {
Dfs1(v[i]);
if (only[u_] == - 1) continue ;
if (! only[u_]) {
only[u_] = only[v[i]];
} else if (only[u_] != only[v[i]]) {
only[u_] = - 1;
}
}
}
//=============================================================
int main() {
int T = read();
for (num = 1; num <= T; ++ num) {
std :: cin >> S[num];
int n = S[num].length(), last = 1;
for (int j = 0; j < n; ++ j) last = Insert(S[num][j] - 'a', last);
}
for (int i = 2; i <= node_num; ++ i) AddEdge(link[i], i);
Dfs1(1);
for (int i = 2; i <= node_num; ++ i) {
if (only[i] != - 1) ans[only[i]] += len[i] - len[link[i]];
}
for (int i = 1; i <= T; ++ i) printf("%d\n", ans[i]);
return 0;
}

算法二

//知识点:广义 SAM
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define ll long long
const int kMaxn = 2e5 + 10;
const int kMaxm = 26;
//=============================================================
std :: string S[kMaxn];
int only[kMaxn << 1], top[kMaxn << 1], sum[kMaxn << 1];
int num, node_num = 1, ch[kMaxn << 1][kMaxm], len[kMaxn <<1], link[kMaxn << 1];
int edge_num, head[kMaxn], v[kMaxn << 1], ne[kMaxn << 1];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void AddEdge(int u_, int v_) {
v[++ edge_num] = v_, ne[edge_num] = head[u_], head[u_] = edge_num;
}
int Insert(int c_, int last_) {
if (ch[last_][c_]) {
int p = last_, q = ch[p][c_];
if (len[p] + 1 == len[q]) {
only[q] = - 1;
return q;
}
int newq = ++ node_num;
memcpy(ch[newq], ch[q], sizeof(ch[q]));
len[newq] = len[p] + 1;
link[newq] = link[q];
link[q] = newq;
for (; p && ch[p][c_] == q; p = link[p]) ch[p][c_] = newq;
only[newq] = num;
return newq;
}
int p = last_, now = ++ node_num;
only[now] = num;
len[now] = len[p] + 1;
for (; p && ! ch[p][c_]; p = link[p]) ch[p][c_] = now;
if (! p) {link[now] = 1; return now;}
int q = ch[p][c_];
if (len[q] == len[p] + 1) {link[now] = q; return now;}
int newq = ++ node_num;
memcpy(ch[newq], ch[q], sizeof(ch[q]));
link[newq] = link[q], len[newq] = len[p] + 1;
link[q] = link[now] = newq;
for (; p && ch[p][c_] == q; p = link[p]) ch[p][c_] = newq;
return now;
}
void Dfs1(int u_) {
for (int i = head[u_]; i; i = ne[i]) {
Dfs1(v[i]);
if (only[u_] == - 1) continue ;
if (! only[u_]) {
only[u_] = only[v[i]];
} else if (only[u_] != only[v[i]]) {
only[u_] = - 1;
}
}
}
void Dfs2(int u_, int top_) {
if (! top_ && only[u_] != - 1) top_ = u_;
top[u_] = top_;
if (top_) sum[u_] += len[u_] - len[link[u_]];
for (int i = head[u_]; i; i = ne[i]) {
Dfs2(v[i], top_);
sum[u_] += sum[v[i]];
}
}
void Work(std :: string S_) {
std :: vector <int> node;
ll ans = 0;
int n = S_.length(), now = 1;
for (int i = 0; i < n; ++ i) {
now = ch[now][S_[i] - 'a'];
if (only[now] != - 1) node.push_back(top[now]);
}
std :: sort(node.begin(), node.end());
for (int i = 0, n = node.size(); i < n; ++ i) {
if (i != 0) {
if (node[i] == node[i - 1]) continue;
}
ans += sum[node[i]];
}
printf("%lld\n", ans);
}
//=============================================================
int main() {
int T = read();
for (num = 1; num <= T; ++ num) {
std :: cin >> S[num];
int n = S[num].length(), last = 1;
for (int j = 0; j < n; ++ j) last = Insert(S[num][j] - 'a', last);
}
for (int i = 2; i <= node_num; ++ i) AddEdge(link[i], i);
Dfs1(1), Dfs2(1, 0);
for (int i = 1; i <= T; ++ i) Work(S[i]);
return 0;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141761.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:4,994
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,472
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,281
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,282
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,840
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,072
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站