神 \(\mathrm{{\color{black}w}{\color{red}{ind\_whisper}}}\) 说 : 我不是 Amy,我对 SAM 没有兴趣.
0.前言
并没怎么看懂WJMZBMR神犇的课件,窝太菜辽...
参考 : 陈立杰 : 后缀自动机 & OI-wiki
感谢 mivik 的 SAM 可视化,我只能说 : 帮大忙了.\(\large\texttt{Link}\)
一个是动态过程但是特别鬼畜的 SAM 可视化 \(\texttt{Link.}\)
感谢 神 \(\mathrm{{\color{black}w}{\color{red}{ind\_whisper}}}\) 一直不学 SAM 才让我不再死等他学完然后看他博客了(大雾)
感谢 神 \(\mathrm{\color{black}{K}\color{red}{HIN}}\) 一直催我催神 \(\mathrm{{\color{black}w}{\color{red}{ind\_whisper}}}\) 学广义SAM(?)
本文是学习笔记而不是具体对 SAM 的介绍,几乎不会出现对性质/时空复杂度的证明.
作者不会排版,观感可能不是那么好...
1.约定
神 \(\mathrm{{\color{black}w}{\color{red}{ind\_whisper}}}\) 说 : SAM 就是一个叫山姆的人发明的自动机.
如果没有特殊说明,那么通常有如下符号 :
\(s\) : 表示要建立SAM / 要求解的字符串.
\(n\) : \(|s| = n\) , 即字符串长度.
子串 : 字符串 \(s\) 中的一个连续段,如无说明,默认为非空的子串.
\(s[l,r]\) : 字符串 \(s\) 从 \(s_l\) 到 \(s_r\) 的子串,一般地,\(l \le r\).
\(\mathrm{suf}(i)\) : 字符串的第 \(i\) 个后缀,代表 从 \(s_i\) 到 \(s_n\) 这一子串.
\(\Sigma\) : 字符集.
\(|\Sigma|\) : 字符集大小.
请跳过以下约定直到你看到 3.自动机 一节.
头铁看完也行.
\(st_i\) : (state) 自动机的一个状态,特别的 \(st_0\) 代表初始状态.
\(null\) : 空状态/非法的状态.
\(\mathrm{trans}(st,ch)\) 转移函数,代表从状态 \(st\) 添加字符 \(ch\) 后转移到的状态,特别的,可能会转移到 \(null\).
请跳过以下约定直到你看到 4.1 SAM的建立 一节.
头铁看完也行.
1.1 SAM 重要约定 endpos
看了一圈发现很多介绍SAM的都管这个叫 right
我太菜了,都是乱学的
\(\mathrm{endpos}(t)\) : 对于一个 \(s\) 的子串 \(t\) , 其在 \(s\) 里结束的位置的集合.
例如 : \(wiwindwhisper\) 的子串 \(wi\) 的 \(\mathrm{endpos}\) 为 \(2,4\).
于是可以发现,有些不同(起止位置不同或者本质不同皆可)子串的 \(\mathrm{endpos}\) 是相同的,这条性质可以优化 SAM 的构造.
例如 \(windwhisper\) 这个串里 \(ind\) 和 \(wind\) 这两个子串的 \(\mathrm{endpos}\),是相同的.
等价类 : 称 \(\mathrm{endpos}\) 相同的子串的集合为一个等价类.
然后是三条引理 (Lemma) :
感觉感性理解一下就能发现不难证明.
\(\mathrm{I}\).对于 \(s\) 的两个子串 \(u,v (|u| \le |v|)\),若 \(\mathrm{endpos}(u) = \mathrm{endpos}(v)\),则 \(u\) 是 \(v\) 的子串,且 \(u\) 在 \(s\) 的每次出现都是以 \(v\) 的子串的形式出现的,反之亦然.
\(\mathrm{II}\). 对于 \(s\) 的两个子串 \(u,v (|u| \le |v|)\),有 :
\[\begin{cases} \operatorname{endpos}(v) \subseteq \operatorname{endpos}(u) & \text{if } u \text{ is a suffix of } v \\ \operatorname{endpos}(u) \cap \operatorname{endpos}(v) = \varnothing & \text{otherwise} \end{cases} \]
\(\mathrm{III}\).将一个等价类中的子串按照长度不增排序后,每个子串都不会比它前一个子串长.
窃以为上面三个引理陈述的都是同样的事实.
1.2 SAM 重要约定 link
对于任意的状态 \(st\) ,其必定对应一个等价类.
现在提取这个等价类中长度最长的子串 \(u\),那么等价类中其他字串都是 \(u\) 的后缀.
但是 \(u\) 的每个后缀不一定都是在这个等价类里的.
举个例子 : \(winin\).
\(win\) 的后缀 \(in\) 的 \(\mathrm{endpos}\) 显然与 \(win\) 不尽相同.
而 \(\mathrm{link}(st)\) 就是连接到等价类最长串的 不在当前等价类里的最长后缀 所在等价类的链接.
然后所有等价类之间都有真子集/真包含关系,要么就是交集为空集.
于是所有 \(\mathrm{link}\) 形成了树形结构.
2.引入
我们看一个题.
给你两个 \(10^6\) 个字符的小写字母串,求它们的最长公共子串.
但是你遇到了非常拉跨的一台评测机...
首先不能使用 \(n \log n\) 的哈希做法了,时间爆炸.
于是早都会了 SA 的神仙们就很不屑,建出 SA 之后就可以 \(\mathcal{O} (n)\) 的求解了,如果使用 DC3 或者 SA-IS 这样的科技,甚至可以做到整体线性求解.
但是 DC3 和 SA-IS 不但太长还很难懂,有没有什么更简单一点的做法?
于是我们引入后缀自动机 (Suffix Automaton - SAM).
3.自动机
首先,可以简单地定义一个自动机为 : 对信号序列(或者更狭隘一些,一个字符串)进行判定的数学模型.
也就是一个能处理字符串的模型.
我们通常研究的自动机都是 确定性有限状态自动机 (DFA).
而建立完成的自动机都可以简单表示为一个有向无环图,结点为状态,边为转移,且总是存在 终止状态.
好的,现在翻回 2.约定 去把关于自动机部分的约定看完.
分隔线分割一下,以提醒你去看约定.
4.后缀自动机
后缀自动机 (Suffix Automaton), 以下简记为 SAM.
顾名思义,后缀自动机是能识别 \(s\) 的所有后缀的模型.
同时,由于子序列可以理解为一个后缀的前缀,SAM也可以识别子串.
4.1 SAM的建立
首先,SAM需要存储 \(s\) 每一个 后缀的信息.
通过之前 AC 自动机的经验可知, trie树是对于多个串的很好的结构.
考虑把 \(s\) 的 \(n\) 个后缀插入 trie,那么光是这一步就是 \(n^2\) 级别的了,并且大大浪费了空间,而 SAM 就是一种将后缀信息高度压缩的建立方式,是能够接受 \(s\) 的全部后缀的自动机中状态最简的.
现在我们来说说为什么 SAM 能接受一个字符串的所有子串.
反证法,对于一个\(s[l,r]\),假设 \(\mathrm{trans}(st_0,s[l,r]) = null\) , 那么 \(\mathrm{suf}(l)\) 必然不能被接受,因为 \(s[l,r]\) 是 \(\mathrm{suf}(l)\) 的一个子串,于是我们证明了 SAM 可以接受子串.
但是把思路引导向子串并不能优化空间,因为子串是 \(n^2\) 级的.
好的,现在翻回 2.约定 去把关于SAM的约定看完.
分隔线分割一下,以提醒你去看约定.
现在读完了吗,辛苦你了,我写博客的顺序应该和你阅读的顺序差不多,所以写到这里我还是对建立 SAM 比较懵的,那么就往下看吧.
先解决一个疑问 : 为什么上面扯的那些约定可以优化建立 SAM ?
因为 \(\mathrm{endpos}\) 是 \(\mathcal{O} (n)\) 级别的.
建立 SAM 是一个在线的过程,即每个字符逐字加入,且加入完一个前缀后相当于已经对这个前缀建立了完整的 SAM 了.
首先为了快速扩展而不是重新从 trie 的根跑下去,记录加入上一个字符后转移到的状态为 \(st_{lst}\).
对于新的字符 \(ch\) ,创建一个全新状态 \(st_{cur}\),且令 \(\mathrm{len}(st_{cur}) = \mathrm{len}(st_{lst}) + 1\).
如果 \(\mathrm{trans}(st_{lst},ch) = null\) 那么就把这个转移设为转移到 \(st_{cur}\).
但是现在我们还没求出 \(\mathrm{link}(cur)\),下面是这个过程.
沿着 \(st_{lst}\) 的 \(\mathrm{link}\) 往父亲跳,找每个不能以 \(ch\) 为转移的状态并且将这些状态以 \(ch\) 为转移的结果连到 \(st_{cur}\), 即令 \(\mathrm{trans}(st_{x},ch) = st_{cur}\).
直到找到一个能以 \(ch\) 为转移的点,假如那个点是 \(st_0\) 那么就把\(\mathrm{link}(st_{cur})\) 设为 \(st_0\) ,然后插入 \(ch\) 的过程就结束了.
上述是为情况 1 : 沿着 \(\mathrm{link}\) 跳到 \(st_0\) 都没有可以转移的.
否则进入下面的流程 :
我们找到的状态 \(st_{p}\) 能使得原本 \(\mathrm{trans}(p,ch) \ne null\) 且 \(st_{p} \ne st_0\).
记 \(\mathrm{trans}(st_{p},ch)\) 为 \(st_q\)
现在分一个类, \(\mathrm{len}(st_p) + 1 = \mathrm{len}(st_q)\) 或者 \(\mathrm{len}(st_p) + 1 \ne \mathrm{len}(st_q)\).
如果相等的话, 令 \(\mathrm{link}(st_{cur}) = st_q\),插入 \(ch\) 的过程就结束了.
上述是为情况 2.
然后就只剩最后的情况 3了.
情况 3 拢共分三步且比较复杂.
-
首先再建立一个结点,记为 \(st_{pp}\).
其继承 \(st_q\) 的所有转移与 \(st_q\) 的 \(\mathrm{link}\),但是不继承 \(\mathrm{len}\),而是将 \(\mathrm{len}(st_{pp})\) 定为 \(\mathrm{len}(st_p) + 1\). -
完成复制后,将 \(\mathrm{link}(st_{cur})\) 和 \(\mathrm{link}(st_q)\) 都指向 \(st_{pp}\).
-
然后从 \(st_p\) 沿着 \(\mathrm{link}\) 往父亲跳,将每个这条返祖链上的 \(\mathrm{trans}(st_{x},ch) = st_{q}\) 改为 \(\mathrm{trans}(st_{x},ch) = st_{pp}\)
上述是为情况 3.
Code :
菜逼不太会指针,于是用的是最简单的数组模拟指针.
struct SuffixAutomaton {
int tot,lst;
SuffixAutomaton() : tot(1),lst(1){}
struct Node {
int len,link;
int ch[26];// depends on |sigma|
}st[N << 1];
inline void insert(int ch) {
int p = lst,cur = ++tot;lst = cur;
st[cur].len = st[p].len + 1;
for(;p && !st[p].ch[ch];p = st[p].link)
st[p].ch[ch] = cur;
if(!p) st[cur].link = 1;
else {
int q = st[p].ch[ch];
if(st[q].len == st[p].len + 1)
st[cur].link = q;
else {
int pp = ++tot;st[pp] = st[q];
st[pp].len = st[p].len + 1;
st[q].link = st[cur].link = pp;
for(;p && st[p].ch[ch] == q;p = st[p].link)
st[p].ch[ch] = pp;
}
}
}
}SAM;
4.2 SAM的特质
-
构造时间为 \(\mathcal{O} (n)\) 级别,但常数较大.
-
因为转移数组需要开到 \(|\Sigma|\) 导致占用空间多于后缀数组.
-
建立完成的 SAM 状态个数不超过 \(2n - 1\),转移个数不超过 \(3n - 4\).
4.3 SAM的应用
模板 : \(\texttt{Link.}\)
求出现次数不为 \(1\) 的子串的出现次数乘其长度.
首先把 SAM 整出来.
然后用 \(\mathrm{link}\) 建一棵树,称为 \(\mathrm{parent}\) 树.
在插入的时候,我们把每个 \(st_{cur}\) 点的权值设为 \(1\),然后可以发现在 \(\mathrm{parent}\) 树上,叶子结点的 \(\mathrm{len}\) 较长 祖先关系即是包含关系,那么在树上统计即可.
int siz[N << 1];
struct SuffixAutomaton {
int tot,lst;
SuffixAutomaton() : tot(1),lst(1){}
struct Node {
int len,link;
int ch[26];// depends on |sigma|
}st[N << 1];
inline void insert(int ch) {
int p = lst,cur = ++tot;lst = cur;
siz[tot] = 1;
st[cur].len = st[p].len + 1;
for(;p && !st[p].ch[ch];p = st[p].link)
st[p].ch[ch] = cur;
if(!p) st[cur].link = 1;
else {
int q = st[p].ch[ch];
if(st[q].len == st[p].len + 1)
st[cur].link = q;
else {
int pp = ++tot;st[pp] = st[q];
st[pp].len = st[p].len + 1;
st[q].link = st[cur].link = pp;
for(;p && st[p].ch[ch] == q;p = st[p].link)
st[p].ch[ch] = pp;
}
}
}
}SAM;
char s[N];
int head[N << 1],ecnt = -1;
struct Edge {
int nxt,to;
}e[N << 1];
inline void AddEdge(int st,int ed) {
e[++ecnt] = (Edge){head[st],ed};
head[st] = ecnt;
}
int ans;
void dfs(int u) {
fe(i,u) {
dfs(e[i].to);
siz[u] += siz[e[i].to];
}
if(siz[u] != 1)
ans = std::max(ans,siz[u] * SAM.st[u].len);
}
不实际建出树,只使用拓扑序的更快做法 :
int siz[N << 1];
struct SuffixAutomaton {
int tot,lst;
SuffixAutomaton() : tot(1),lst(1){}
struct Node {
int len,link;
int ch[26];// depends on |sigma|
}st[N << 1];
inline void insert(int ch) {
int p = lst,cur = ++tot;lst = cur;
siz[tot] = 1;
st[cur].len = st[p].len + 1;
for(;p && !st[p].ch[ch];p = st[p].link)
st[p].ch[ch] = cur;
if(!p) st[cur].link = 1;
else {
int q = st[p].ch[ch];
if(st[q].len == st[p].len + 1)
st[cur].link = q;
else {
int pp = ++tot;st[pp] = st[q];
st[pp].len = st[p].len + 1;
st[q].link = st[cur].link = pp;
for(;p && st[p].ch[ch] == q;p = st[p].link)
st[p].ch[ch] = pp;
}
}
}
}SAM;
char s[N];
int buc[N << 1];
int id[N << 1];
int mian() {
init_IO();
int n = getStr(s + 1);
ff(i,1,n) SAM.insert(s[i] - 'a');
ff(i,1,SAM.tot) ++buc[SAM.st[i].len];
ff(i,1,n) buc[i] += buc[i - 1];
fb(i,SAM.tot,1) id[buc[SAM.st[i].len]--] = i;
fb(i,SAM.tot,1) siz[SAM.st[id[i]].link] += siz[id[i]];
int ans = 0;
ff(i,1,SAM.tot) if(siz[i] > 1)
ans = std::max(ans,SAM.st[i].len * siz[i]);
write(ans);
end_IO();
return 0;
}
做一切SA题
卡空间当我没说.
当然有些题用 SA 更简单。
判断模式串是否出现
直接从初始结点开始转移即可.
然后拿去做AC自动机模板
求本质不同子串个数
首先,SAM可以接受所有的子串且没有多余的部分.
那么本质不同字串个数就是 SAM 上以 \(st_0\) 为起点的路径条数.
或者统计每个结点对应的子串数量,就是 \(\mathrm{len}(u) - \mathrm{len(link}(u))\)
\(\uparrow\) 这个题 SAM 不如 SA 快,笑嘻了.
动态求,每次求SA的做法就不行了,要用SA还要倒着建然后做 RMQ,乐.
记得把 SAM 的 ch 换成 std::map.
然后这个题 std::map 快于 std::unordered_map 快于 __gnu_pbds::gp_hash_table.
字典序第 k 大子串
首先子串就是路径.
然后就是第 \(k\) 大路径了.
本质不同子串就注意一下 siz.
SP7258 SUBLEX - Lexicographical Substring Search
4.4 SAM 例题
5 广义SAM
神 \(\mathrm{{\color{black}w}{\color{red}{ind\_whisper}}}\) 说 : 广义 SAM 就是一个叫 SAM 的人推广的自动机.
广义SAM (general SAM) 山姆将军 是一种直接利用trie树的优秀结构建立的SAM,特点是适合解决多个串问题.
5.1 错误的建立方式
-
在多个串之间插入空字符形成一个长的单串,然后对这个串建立一般的 SAM.
-
每次插入一个字符串之前将
lst设为1
这两类做法在没有特判空结点和可行转移的前提下,直接通过普通SAM魔改,就是错误的.
5.2 正确的建立方式
首先把所有的字符串插入一颗 trie 树.
为了不像错误做法一样重复建立同样意义的结点,我们在 trie 树上 BFS 并且保留先前的 cur 来继续建立 SAM.
Code :
struct GeneralSuffixAutomaton {
int tot;
struct Node {
int len,link;
int ch[26];
}st[N << 1];
GeneralSuffixAutomaton() : tot(1) {}
inline int extend(int ch,int p) {
int cur = st[p].ch[ch];
if(st[cur].len) return cur;
st[cur].len = st[p].len + 1;p = st[p].link;
for(;p && !st[p].ch[ch];p = st[p].link)
st[p].ch[ch] = cur;
if(!p) st[cur].link = 1;
else {
int q = st[p].ch[ch];
if(st[q].len == st[p].len + 1)
st[cur].link = q;
else {
int pp = ++tot;
ff(i,0,25)
st[pp].ch[i] = (st[st[q].ch[i]].len ? st[q].ch[i] : 0);
st[pp].len = st[p].len + 1;
st[pp].link = st[q].link;
st[q].link = st[cur].link = pp;
for(;p && st[p].ch[ch] == q;p = st[p].link)
st[p].ch[ch] = pp;
}
}
return cur;
}
inline void insert(char *s) {
int p = 1;
for(int i = 0;s[i];++i) {
if(!st[p].ch[s[i] - 'a'])
st[p].ch[s[i] - 'a'] = ++tot;
p = st[p].ch[s[i] - 'a'];
}
}
inline void build() {
std::queue<pii> q;
ff(i,0,25) if(st[1].ch[i])
q.push(std::make_pair(i,1));
while(!q.empty()) {
pii u = q.front();q.pop();
int lst = extend(u.first,u.second);
ff(i,0,25) if(st[lst].ch[i])
q.push(std::make_pair(i,lst));
}
}
inline void solve() {
ll ans = 0;
ff(i,1,tot)
ans += st[i].len - st[st[i].link].len;
write(ans),enter;
}
}SAM;
5.3 例题
依然是利用等价类求即可 \(\sum \mathrm{len}(i) - \mathrm{len}(\mathrm{link(i)})\)
彩蛋(?)
你在看到一半的时候看到提醒你去看约定之后上下来回翻真的很像在自动机上转移(大雾).