后缀自动机 学习笔记
Visits: 891
因为 SA 就很有用了,所以一直不想学 SAM。突然不知道为什么就想学了,可能是为了吊打兔兔吧。
后缀自动机 (SAM) 是一个能解决许多字符串相关问题的有力的数据结构。
直观上,SAM 可以理解为将字符串的所有子串高度压缩至理论复杂度下界 $\mathcal O(n)$ 的形式。
确定有限状态自动机 (DFA)
我们先要了解,什么是确定有限状态自动机 (DFA)。
定义
一个 DFA 可以看成一张有向图,由五个部分构成:
- 状态集合 $Q$:图中的点。
- 字符集 $\Sigma$:所有合法字符的集合。
- 转移函数 $\delta(v,c)$:图中的边,其中 $v$ 和返回值都是一个状态,分别对应一条边的起点和终点,$c \in \Sigma$,表示这条边上的字符。
- 起始状态 $S$:$S \in Q$,是一个特殊的状态。
- 接受状态集合 $F$:$F \subseteq Q$,是一组特殊的状态。
作用
DFA 可以识别字符串。
当 DFA 读入字符串 $s$ 时,从 $S$ 开始按照 $\delta(v,c)$ 一个一个字符地转移。
特别地,如果某个状态 $v$ 没有字符 $c$ 的转移,则令 $\delta(v,c) = N$,$N$ 只能转移到 $N$,且 $N \notin F$。
如果读入完 $s$ 后处在 $F$ 内,就称这个 DFA 接受 $s$。
扩展定义转移函数 $\delta(v,s)$,其中 $s$ 是一个由 $\Sigma$ 内的字符构成的字符串,则 $\delta(v,s) = \delta(\delta(v,s[1]),s[2:|s|])$。
一个 DFA 是否接受 $s$,等价于求 $[\delta(S, s) \in F]$ 的值。
后缀自动机 (SAM)
后缀自动机 (SAM) 是接受且仅接受字符串 $s$ 的所有后缀的最小 DFA。
构造
$\operatorname{rightpos}$ 等价类
在一些教程中,$\operatorname{rightpos}$ 也被称作 $\operatorname{endpos}$。本文选择 $\operatorname{rightpos}$,是因为同样存在定义类似的 $\operatorname{leftpos}$,而不存在 $\operatorname{beginpos}$ 的叫法。
对于 $s$ 的子串 $t$,记 $\operatorname{rightpos}(t)$ 为 $s$ 中 $t$ 的所有结束(即最右边的字符)位置。如对于字符串 $\texttt{abcbc}$,$\operatorname{rightpos}(\texttt{bc}) = 3,5$。特别地,空串的 $\operatorname{rightpos}$ 定义为 $0,1,\cdots,|s|$。
若两个非空子串 $t_1,t_2$,满足 $\operatorname{rightpos}(t_1) = \operatorname{rightpos}(t_2)$,则将他们划分到一个 $\operatorname{rightpos}$ 等价类中。
SAM 中的每个状态都对应着一个 $\operatorname{rightpos}$ 等价类,其中 $S$ 对应着空串所在的等价类。
$\operatorname{rightpos}$ 性质
- 考虑一个子串 $t$,我们每次去掉 $t$ 的首字母,则它所在的 $\operatorname{rightpos}$ 要么不变,要么会增加若干个新位置。
形式化地,对于两个子串 $t_1,t_2$,不妨设 $|t_1| \le |t_2|$:
若 $t_1$ 为 $t_2$ 的后缀,则 $\operatorname{rightpos}(t_2) \subseteq \operatorname{rightpos}(t_1)$;
否则,说明 $t_2$ 所在的位置 $t_1$ 都不在,即 $\operatorname{rightpos}(t_1) \cap \operatorname{rightpos}(t_2) = \varnothing$。 - 反过来考虑更强一点的性质,如果若干个子串的 $\operatorname{rightpos}$ 一样,意味着它们在 $s$ 中的出现位置一样,且它们一定是由一个子串 $t$ 不断去掉首字母,但还未能增加新位置时的所有子串构成的。
因此,在一个 $\operatorname{rightpos}$ 等价类中,较短的子串为较长的子串的后缀,且所有子串的长度恰好覆盖一个区间。
后缀链接 $\operatorname{parent}$
对于一个不是 $S$ 的状态 $v$,设它对应的等价类中最短的子串为 $t$。
后缀链接 $\operatorname{parent}(v) = \operatorname{rightpos}(t[2:|t|])$。
另外,对于一个状态 $v$,记 $\operatorname{len}(v)$ 表示它对应的等价类中最长的子串的长度。特别的,$\operatorname{len}(S) = 0$。
$\operatorname{parent}$ 性质
- 依然考虑不断去掉一个子串 $t$ 的首字母:
如果还未能增加新位置,则还在同一个 $\operatorname{rightpos}$ 等价类中;
否则,会跳到其 $\operatorname{parent}$ 等价类中。
因此,对于一个不是 $S$ 的状态 $v$,将其视作 $\operatorname{rightpos}$ 集合,有 $v \subseteq \operatorname{parent}(v)$。 - 根据上条性质,对于一个不是 $S$ 的状态 $v$,它对应的 $\operatorname{rightpos}$ 等价类中,子串的长度区间为 $(\operatorname{len}(\operatorname{parent}(v)), \operatorname{len}(v)]$,即 $v$ 对应的子串数量为 $\operatorname{len}(v) – (\operatorname{len}(\operatorname{parent}(v))$。
- 所有 $\operatorname{parent}$ 构成一棵以 $S$ 为根的树,我们称其为 $\operatorname{parent}$ 树。
构造 SAM
一开始 SAM 只包含一个状态 $S$,编号为 $0$。为了方便,不妨令 $\operatorname{parent}(S) = -1$。
考虑依次添加字符,同时维护每个状态的 $\operatorname{len}$,$\operatorname{parent}$ 和转移。
令 $l$ 表示任意时刻整个字符串对应的状态,每次添加一个字符 $c$ 的过程如下:
- 创建一个新的状态 $w$,并将 $\operatorname{len}(w)$ 设为 $\operatorname{len}(l) + 1$。
- 从 $l$ 开始遍历 $\operatorname{parent}$:
- 如果当前状态不存在字符 $c$ 的转移,则添加一个到 $w$ 的转移。
- 如果当前状态存在字符 $c$ 的转移,则将这个状态标记为 $p$,转移到的状态标记为 $q$,然后跳出遍历。
- 接下来有三种情况:
- 如果始终没有状态存在字符 $c$ 的转移,则将 $\operatorname{parent}(w)$ 设为 $0$,然后退出。
- 否则,若 $\operatorname{len}(p) + 1 = \operatorname{len}(q)$,则将 $\operatorname{parent}(w)$ 设为 $q$,然后退出。
- 否则,再创建一个新的状态 $k$,将 $q$ 的 $\operatorname{parent}$ 和转移复制到 $k$ 上,将 $\operatorname{len}(k)$ 设为 $\operatorname{len}(p) + 1$,将 $\operatorname{parent}(w)$ 和 $\operatorname{parent}(q)$ 都设为 $k$。然后从 $p$ 往回遍历 $\operatorname{parent}$,若存在到 $q$ 的转移,则将转移重定向到 $k$ 上。
- 更新 $l$,即将 $l$ 设为 $w$。
最后,我们再从 $l$ 遍历一次 $\operatorname{parent}$,则 $F$ 即由遍历到的状态构成。
复杂度
如果转移用 map
存储,则时间复杂度为 $\mathcal O(n \log |\Sigma|)$,空间复杂度为 $\mathcal O(n)$。
如果转移用数组存储,同时借助链表,则时间复杂度为 $\mathcal O(n)$,空间复杂度为 $\mathcal O(n |\Sigma|)$。如果不借助链表,时间复杂度为 $\mathcal O(n |\Sigma|)$,空间复杂度为 $\mathcal O(n |\Sigma|)$。
状态数和转移数上界
对于 $|s| \ge 2$ 的字符串,状态数 $\le 2 |s| – 1$,上界可以在 $\texttt{abb}\dots\texttt{b}$ 达到。
对于 $|s| \ge 3$ 的字符串,转移数 $\le 3 |s| – 4$,上界可以在 $\texttt{abb}\dots\texttt{bc}$ 达到。
性质
- $s$ 的子串和 SAM 中从 $S$ 开始的路径一一对应。
对于一个非 $S$ 状态 $v$,$v$ 对应的 $\operatorname{rightpos}$ 等价类大小 $=$ $v$ 对应的子串数量 $=$ 从 $S$ 开始到 $v$ 的路径数量 $=$ $\operatorname{len}(v) – (\operatorname{len}(\operatorname{parent}(v))$。 - 称 $s$ 的前缀在 SAM 上对应的节点为终点节点。
对于一个非 $S$ 状态 $v$,$v$ 对应的 $\operatorname{rightpos}$ 集合 $=$ 其 $\operatorname{parent}$ 树的子树内的终点节点所对应前缀的位置 $=$ $v$ 对应的子串在 $s$ 中出现的位置。
根据此条性质,我们可以方便地采用线段树合并求出 $\operatorname{rightpos}$ 集合。 - 说白了,SAM 中的概念,包括 $\operatorname{rightpos}$、$\operatorname{parent}$、终点节点、前缀、后缀、子串、路径,全都能串起来。
串起来之后,随便组合就有各种各样的性质。
例如,$s$ 的任意两个前缀对应的终点节点在 $\operatorname{parent}$ 树上的 LCA 所对应的最长子串就是这两个前缀的最长公共后缀。
应用
【模板】P3804 【模板】后缀自动机 (SAM)
根据:
- 对于一个非 $S$ 状态 $v$,$v$ 对应的 $\operatorname{rightpos}$ 集合 $=$ 其 $\operatorname{parent}$ 树的子树内的终点节点所对应前缀的位置 $=$ $v$ 对应的子串在 $s$ 中出现的位置。
每个前缀所在的状态有贡献 $1$。
那么,对每个状态求出其 $\operatorname{parent}$ 树上的子树贡献和,然后乘上这个状态的 $\operatorname{len}$,最后取 $\max$ 即可。
const int N = 1e6 + 7;
struct SAM {
int n, l, ch[N<<1][26], len[N<<1], pa[N<<1], t;
char s[N];
inline void init() { pa[0] = -1; }
inline void add(int c) {
int w = ++t, p = l;
len[w] = len[l] + 1;
while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
if (!~p) return pa[l=w] = 0, void();
int q = ch[p][c];
if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
int k = ++t;
pa[k] = pa[q], memcpy(ch[k], ch[q], sizeof(ch[k]));
len[k] = len[p] + 1, pa[w] = pa[q] = k;
while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
l = w;
}
inline void build() {
init();
for (int i = 1; i <= n; i++) add(s[i] - 'a');
}
int cnt[N<<1];
ll ans;
vi e[N<<1];
void dfs(int x) {
for (int y : e[x]) dfs(y), cnt[x] += cnt[y];
if (cnt[x] > 1) ans = max(ans, 1ll * cnt[x] * len[x]);
}
inline void calc() {
for (int i = 1, p = 0; i <= n; i++) p = ch[p][s[i]-'a'], ++cnt[p];
for (int i = 1; i <= t; i++) e[pa[i]].pb(i);
dfs(0), print(ans);
}
} sam;
int main() {
rds(sam.s, sam.n);
sam.build(), sam.calc();
return 0;
}
【例题】P4070 [SDOI2016]生成魔咒
动态子串数。
每加入一个字符,本质不同的子串数就会加 $\operatorname{len}(l) – \operatorname{len}(\operatorname{parent}(k))$ 个。
【例题】SP7258 SUBLEX – Lexicographical Substring Search
第 $k$ 小子串。
由于 SAM 是个 DAG,因此设 $cnt_i$ 表示从 $i$ 开始的路径条数,拓扑排序后再 DAG 上 dp。
这里拓扑排序可以利用基数排序,借助转移一定是从 $\operatorname{len}$ 小的往大的即可。
找答案时,从根开始贪心地找。
const int N = 9e4 + 7;
struct SAM {
int n, l, len[N<<1], pa[N<<1], t;
char s[N];
map<char, int> ch[N<<1];
inline void init() { pa[0] = -1; }
inline void add(char c) {
int w = ++t, p = l;
len[w] = len[l] + 1;
while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
if (!~p) return pa[l=w] = 0, void();
int q = ch[p][c];
if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
int k = ++t;
pa[k] = pa[q], ch[k] = ch[q];
len[k] = len[p] + 1, pa[w] = pa[q] = k;
while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
l = w;
}
inline void build() {
init();
for (int i = 1; i <= n; i++) add(s[i]);
}
int b[N<<1], c[N];
ll cnt[N<<1];
inline void sort() {
for (int i = 1; i <= t; i++) ++c[len[i]];
for (int i = 1; i <= n; i++) c[i] += c[i-1];
for (int i = 1; i <= t; i++) b[c[len[i]]--] = i;
for (int i = t; ~i; i--) {
int x = b[i];
cnt[x] = 1;
for (auto o : ch[x]) cnt[x] += cnt[o.se];
}
}
inline void ask(int x) {
int p = 0;
while (x)
for (auto o : ch[p])
if (x - cnt[o.se] > 0) x -= cnt[o.se];
else {
putchar(o.fi), p = o.se, --x;
break;
}
putchar('\n');
}
} sam;
int main() {
rds(sam.s, sam.n), sam.build(), sam.sort();
int q, x;
rd(q);
while (q--) rd(x), sam.ask(x);
return 0;
}
【例题】SP1811 LCS – Longest Common Substring
两个串的最大公共子串。
对第一个串建 SAM,然后依次加入第二个串的字符,求当前第二个串的是第一个串的子串的最长后缀。
用一个指针记录当前解在 SAM 上的位置,加入一个字符时先看能不能匹配,如果能就直接匹配,不能就暴力跳 $\operatorname{parent}$,直到可以匹配为止。
每次的解取 $\max$ 即为最优解。
const int N = 2.5e5 + 7;
struct SAM {
int n, l, len[N<<1], pa[N<<1], t;
char s[N];
map<char, int> ch[N<<1];
inline void init() { pa[0] = -1; }
inline void add(char c) {
int w = ++t, p = l;
len[w] = len[l] + 1;
while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
if (!~p) return pa[l=w] = 0, void();
int q = ch[p][c];
if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
int k = ++t;
pa[k] = pa[q], ch[k] = ch[q];
len[k] = len[p] + 1, pa[w] = pa[q] = k;
while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
l = w;
}
inline void build() {
init();
for (int i = 1; i <= n; i++) add(s[i]);
}
int op, ol, ans;
inline void calc(char c) {
while (op && !ch[op][c]) op = pa[op], ol = len[op];
if (ch[op][c]) op = ch[op][c], ++ol;
ans = max(ans, ol);
}
} sam;
char s[N];
int n;
int main() {
rds(sam.s, sam.n), sam.build();
rds(s, n);
for (int i = 1; i <= n; i++) sam.calc(s[i]);
print(sam.ans);
return 0;
}
【例题】SP10570 LONGCS – Longest Common Substring
多个串的最大公共子串。
依然对第一个串建 SAM,类似两个串的情况,将其他串放到 SAM 上匹配。
维护 SAM 每个状态的最长匹配长度,每次的解取 $\min$,所有状态取 $\max$ 即可。
const int N = 1e4 + 7;
char s[N];
int n, ans[N<<1];
struct SAM {
int n, l, ch[N<<1][26], len[N<<1], pa[N<<1], t;
char s[N];
inline void init() {
for (int i = 0; i <= t; i++)
memset(ch[i], 0, sizeof(ch[i]));
t = l = len[0] = 0, pa[0] = -1;
}
inline void add(int c) {
int w = ++t, p = l;
len[w] = len[l] + 1;
while (~p && !ch[p][c]) ch[p][c] = w, p = pa[p];
if (!~p) return pa[l=w] = 0, void();
int q = ch[p][c];
if (len[p] + 1 == len[q]) return pa[l=w] = q, void();
int k = ++t;
pa[k] = pa[q], memcpy(ch[k], ch[q], sizeof(ch[k]));
len[k] = len[p] + 1, pa[w] = pa[q] = k;
while (~p && ch[p][c] == q) ch[p][c] = k, p = pa[p];
l = w;
}
inline void build() {
init();
for (int i = 1; i <= n; i++) add(s[i] - 'a');
}
int b[N<<1], c[N];
inline void sort() {
for (int i = 1; i <= n; i++) c[i] = 0;
for (int i = 1; i <= t; i++) ++c[len[i]];
for (int i = 1; i <= n; i++) c[i] += c[i-1];
for (int i = 1; i <= t; i++) b[c[len[i]]--] = i;
}
int op, ol, ans[N<<1];
inline void calc(int c) {
while (op && !ch[op][c]) op = pa[op], ol = len[op];
if (ch[op][c]) op = ch[op][c], ++ol, ans[op] = max(ans[op], ol);
}
inline void update() {
for (int i = t; i; i--) {
int x = b[i];
ans[pa[x]] = max(ans[pa[x]], min(ans[x], len[pa[x]]));
::ans[x] = min(::ans[x], ans[x]), ans[x] = 0;
}
}
} sam;
inline void solve() {
int m;
rd(m), rds(sam.s, sam.n), sam.build(), sam.sort();
for (int i = 1; i <= sam.t; i++) ans[i] = 1e9;
while (--m) {
rds(s, n), sam.op = sam.ol = 0;
for (int i = 1; i <= n; i++) sam.calc(s[i] - 'a');
sam.update();
}
print(*max_element(ans + 1, ans + sam.t + 1));
}
int main() {
int T;
rd(T);
while (T--) solve();
return 0;
}
参考资料
- OI Wiki 后缀自动机 (SAM)
- OI Wiki 自动机
- EternalAlexander 炫酷后缀树魔术
- 张天扬 后缀自动机及其应用
- 吴作同 后缀自动机的理解与运用
suiqingying
2020年3月26日 上午10:40
很精致