SAM 学习笔记
chaynflow
·
·
算法·理论
SAM
定义
简单地说，SAM 是一个能接受 s 所有状态的最小 DFA。
SAM 形态上是一个 DAG，有源点 t_0，从他出发可以到达所有点。
「转移」就是 DAG 上的边，所有没有「转移」的边都是终止状态，他们是 s 的后缀。
基本性质
每个 s 的子串，都对应一条从 t_0 出发的路径。
endpos
比如 $s = \text{abcab},t=\text{ab}$，$\operatorname{endpos}(t) = \{1,4\}$（下标从 $0$ 开始）。
一些重要的性质：
### 1.若 $\text{endpos}(t') = \text{endpos}(t)$（设 $|t'|<|t|$），当且仅当 $t'$ 的每次出现都为 $t$ 的后缀形式。
证明显然。
### 2.若 $|t'|<|t|$，则 $\text{endpos}(t) \cap \text{endpos}(t') = \varnothing$ 或 $\text{endpos}(t) \sube \text{endpos}(t')$。
第二种情况是 $t'$ 是 $t$ 的后缀，否则为第一种。
证明显然。
### 3.$\text{endpos}$ 等价类长度区间连续，覆盖 $[\text{minlen}(S),\text{len}(S)]$。
证明：设一个等价类的集合为 $u$。
若 $|u| = 1$，显然成立。
若 $|u| > 1$，找到 $u$ 中最长的串 $t$ 与最短的串 $t'$。
有性质 1 可知 $t'$ 是 $t$ 的后缀，且仅作为 $t$ 的后缀出现。
考察长度在 $(\text{minlen}(u),\text{len}(u))$ 内的 $t$ 的后缀串，设为 $t_x$。
由于更短的 $t'$ 与 $t$ 在同一集合内，且 $t_x$ 出现次数应该在 $t$ 与 $t'$ 之间，故 $t_x$ 的出现次数 $=$ $t$ 的出现次数。
再次运用性质 1，可知 $t_x \in u$。
证毕。
---
先插入一个概念再来看性质 4、5。
## 后缀链接 link
后缀链接 $\text{link}(u)$ 表示对应到 $t$ 的不在 $u$ 中的最长后缀对应的 endpos 等价类。
比如 $s = \text{abcab},t=\text{ab}$，$\operatorname{link}(\{4\})$（$\{\text{cab},\text{bcab},\text{abcab}\}$） $= \{1,4\}$（$\{\text{b},\text{ab}\}$）。
可以认为初始状态 $t_0$ 的等价类就是他自己。规定 $\text{endpos}(t_0) = \{-1,0,1,\dots,|s|-1\}$。
### 4.$\text{link}$ 连成一棵树。
证明：每次跳 $\text{link}$ 都会到 $len$ 更短的状态（性质 3，link 的定义），故一定会到 $t_0$。
### 5.$\text{link}$ 连成的树就是 $\text{endpos}$ 的包含关系树。
证明：由性质 2 知 $\text{endpos}$ 会连成树。
考察非 $t_0$ 状态 $u$，由 link 的定义和性质 2 可知：
$$
\text{endpos}(u)\subsetneq \text{endpos}(\text{link}(u)),
$$
这里是 $\subsetneq$，因为若相等，则应该被合并为一个节点。
结合前面的性质，可知命题成立。
## 代码实现
请保证在理解了前面的知识下再来看。
首先定义结构体与框架。
```cpp
struct state {int len, link, nxt[26];};
namespace SAM
{
state st[N << 1];
void init()
{
}
void insert(char c)
{
}
}
```
一开始 SAM 只有一个节点 $t_0$，代码中编号为 $0$，以后的节点从 $1$ 开始往下编。
定义 $st[0].link = -1$，表示连接到虚拟状态，$st[0].len = 0$。
### 插入
假设来了一个字符 $c$，我们如何插入它？（记 `C = c - 'a'`，一个节点的后缀表示该点代表的 endpos 集合的最长的字符串的后缀）
1. 记 $last$ 为上一次操作后，整个字符串对应的节点（初始为 $0$）。
2. 新建一个状态 $cur$，$st[cur].len \gets st[last].len + 1$。
3. 接着令 $p\gets last$，遍历 $p \gets st[p].link$，如果没有 $st[p].nxt[C]$，就加入一个到 $cur$ 的转移（$link$ 遍历到的都是后缀，都需要加入到 $cur$ 的转移）；若存在则进行下一步。
4. 若 $p = -1$，说明之前没有人有 $C$ 这个转移，令 $st[cur].link \gets 0$，退出。
5. 否则说明我们能找到 $p$，记 $st[p].nxt[C] = q$。
6. 若 $st[p].len + 1 = st[q].len$，说明 $q$ 刚好是 $cur$ 的一个后缀（可以由 $p$ 是 $last$ 的后缀得到），直接 $st[cur].link \gets q$ 即可。
7. 否则我们需要「分离」$q$ ，造出一个 $len = st[p].len+1$ 的状态，新建一个状态 $clone$，复制 $q$ 除 $len$ 以外的信息，$st[clone].len = st[p].len + 1$，由于 $clone$ 是 $q$ 的后缀，所以从 $p$ 往上跳到的节点的 $nxt[C]$ 都要改成 $clone$，接着将 $st[q].link \gets clone$，这样就可以 $st[cur].link \gets clone$ 了。
8. 最后更新 $last \gets cur$ ，完成全部过程。
### 代码
```cpp
struct state {int len, link, nxt[26];};
namespace SAM
{
state st[N << 1];
int cnt, last;
void init()
{
st[0].len = 0; st[0].link = -1;
cnt = 0; last = 0;
}
void insert(char c)
{
int cur = ++cnt, C = c - 'a';
st[cur].len = st[last].len + 1;
int p = last;
while (p != -1 && !st[p].nxt[C])
{
st[p].nxt[C] = cur;
p = st[p].link;
}
if (p == -1)
st[cur].link = 0;
else
{
int q = st[p].nxt[C];
if (st[p].len + 1 == st[q].len)
st[cur].link = q;
else
{
int clone = ++cnt;
st[clone] = st[q];
st[clone].len = st[p].len + 1;
while (p != -1 && st[p].nxt[C] == q)
{
st[p].nxt[C] = clone;
p = st[p].link;
}
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
}
```
这是一个 $O(n)$ 的在线算法。
## 应用
### 不同子串个数
有两种方法。
1. 观察 SAM 的结构，可以发现是 DAG，直接 dp。
2. 观察 $link$ 的结构，已知这是一棵树，又能发现 $u$ 节点的子串数量刚好是 $st[u].len - st[st[u].link].len$，求和即可。——（1）
一般用第二种。
### 子串（节点）出现次数
延续 $link$ 的思想，可以发现，若将所有每次新增的节点（不包括 $clone$）的点权全设为 $1$，一个节点的出现次数正好是 $link$ 的子树和。读者自证不难。
### [【模板】后缀自动机（SAM）](https://www.luogu.com.cn/problem/P3804)
直接用上方的思路即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
const int N = 1e6 + 5;
struct state {/*同上*/};
namespace SAM
{
state st[N << 1];
int cnt, last, sz[N << 1];
void init()
{
// 同上
}
void insert(char c)
{
int cur = ++cnt, C = c - 'a';
st[cur].len = st[last].len + 1;
sz[cur] = 1;
// 同上
}
}
string s;
int n, a[N << 1], tot[N];
int main()
{
#ifdef ONLINE_JUDGE
FASTIO;
#endif
cin >> s; SAM::init(); n = s.size();
for (int i = 0; i < n; i++) SAM::insert(s[i]);
long long ans = 0;
for (int i = 1; i <= SAM::cnt; i++) tot[SAM::st[i].len]++;
for (int i = 1; i <= SAM::cnt; i++) tot[i] += tot[i-1];
for (int i = 1; i <= SAM::cnt; i++) a[tot[SAM::st[i].len]--] = i;
// 按照 len 排序，性质 4 的证明是依据
for (int i = SAM::cnt; i; i--)
{
int u = a[i]; SAM::sz[SAM::st[u].link] += SAM::sz[u];
if (SAM::sz[u] > 1) ans = max(ans, 1ll * SAM::st[u].len * SAM::sz[u]);
}
cout << ans;
return 0;
}
```
### [ [SDOI2016] 生成魔咒](https://www.luogu.com.cn/problem/P4070)
考虑单次的增量。
由（1）可知，插入后与插入前相差的子串个数应该就是多出的 $st[cur].len - st[st[cur].link].len$。
注意要开 map 存转移。
```cpp
struct state
{
int len, link;
map <int, int> nxt;
};
namespace SAM
{
/* 自行完成 */
}
int n;
int main()
{
#ifdef ONLINE_JUDGE
FASTIO;
#endif
cin >> n; SAM::init(); long long ans = 0;
for (int i = 1, x; i <= n; i++)
{
cin >> x;
SAM::insert(x);
ans += SAM::st[SAM::last].len - SAM::st[SAM::st[SAM::last].link].len;
cout << ans << "\n";
}
return 0;
}
```
### 第 k 小子串
由前一个思路，我们可以知道每个节点代表的子串数。
接着按转移进行累加即可。
接下来就容易了，直接从 $t_0$ 开始即可。
### [[TJOI2015] 弦论](https://www.luogu.com.cn/problem/P3975)
首先建出 SAM。
若 $t=0$，相当于考虑从 $u$ 出发能到达的子串个数，也就是把除了 $t_0$ 的点的点权设为 $1$ 后从 DAG 上能到达的点的点权和。
若 $t=1$，相当于点权为对应的 endpos 等价类的大小。
```cpp
namespace SAM
{
state st[N << 1];
int cnt, last, sz[N << 1], sum[N << 1];
void init()
{
/* 自行完成 */
}
void insert(char c)
{
/* 自行完成 */
}
}
string s;
int n, t, k, a[N << 1], tot[N];
void prt(int u, int k)
{
if (k <= SAM::sz[u]) return;
k -= SAM::sz[u];
for (int i = 0; i < 26; i++)
{
int v = SAM::st[u].nxt[i];
if (!v) continue;
if (k > SAM::sum[v]) {k -= SAM::sum[v]; continue;}
cout << (char)('a' + i); prt(v, k); return;
}
}
int main()
{
#ifdef ONLINE_JUDGE
FASTIO;
#endif
cin >> s >> t >> k; SAM::init(); n = s.size();
for (int i = 0; i < n; i++) SAM::insert(s[i]);
for (int i = 1; i <= SAM::cnt; i++) tot[SAM::st[i].len]++;
for (int i = 1; i <= SAM::cnt; i++) tot[i] += tot[i-1];
for (int i = 0; i <= SAM::cnt; i++) a[tot[SAM::st[i].len]--] = i;
for (int i = SAM::cnt; i >= 0; i--) SAM::sz[SAM::st[a[i]].link] += SAM::sz[a[i]];
for (int i = 1; i <= SAM::cnt; i++)
t ? SAM::sum[i] = SAM::sz[i] : SAM::sum[i] = SAM::sz[i] = 1;
SAM::sz[0] = SAM::sum[0] = 0;
for (int i = SAM::cnt; i >= 0; i--) for (int j = 0; j < 26; j++)
if (SAM::st[a[i]].nxt[j]) SAM::sum[a[i]] += SAM::sum[SAM::st[a[i]].nxt[j]];
if (SAM::sum[0] < k) cout << "-1";
else prt(0, k);
return 0;
}
```
练习：[SUBLEX - Lexicographical Substring Search](https://www.luogu.com.cn/problem/SP7258)
### LCS(substring)
记两个串为 $s,t$。
首先建出 $s$ 串的 SAM。
然后相当于在 $s$ 串上跑 $t$ 的匹配。
考虑对每一个 $t$ 的前缀，算出他最长的在 $s$ 中出现的后缀。
记 $u$ 表示当前节点，$l$ 表示匹配长度，$C$ 表示当前字符需要的转移。
+ 若 $u$ 有 $nxt[C]$ 的转移，$l \gets l + 1$，$u \gets st[u].nxt[C]$ 即可，否则进行下一步。
+ 若 $u$ 已经到达 $-1$，说明无法匹配，令 $u \gets 0, l \gets 0$ 即可，否则需要缩短要匹配的后缀，令 $u \gets st[u].link,l \gets st[u].len$，返回上一步。
代码：
```cpp
void match(string s)
{
memset(mat, 0, sizeof(mat));
int u = 0, l = 0;
for (int i = 0; i < (int)s.size(); i++)
{
int C = s[i] - 'a';
while (u != -1 && !st[u].nxt[C]) u = st[u].link, l = st[u].len;
if (u != -1) l++, u = st[u].nxt[C];
else u = l = 0;
mat[i] = l;
}
}
```
练习：[LCS - Longest Common Substring](https://www.luogu.com.cn/problem/SP1811)
### 配合线段树合并
### [Security](https://www.luogu.com.cn/problem/CF1037H)
考虑最优方案就是尽量多匹配 $x$ 的前缀，再接上一个比 $x$ 下一个字符大的字符。
首先建出 $s$ 的 SAM，利用线段树合并在 $link$ 树上求出 endpos 等价类的集合。
```cpp
int merge(int u, int v, int l, int r)
{
if (!u || !v) return u + v;
if (l == r) return u;
int ret = ++cnt;
ls[ret] = merge(ls[u], ls[v], l, mid);
rs[ret] = merge(rs[u], rs[v], mid + 1, r);
return ret;
}
void modify(int &u, int l, int r, int a)
{
u = ++cnt;
if (l == r) return;
if (a <= mid) modify(ls[u], l, mid, a);
else modify(rs[u], mid + 1, r, a);
}
bool query(int u, int l, int r, int a, int b)
{
if (!u) return 0;
if (a <= l && r <= b) return 1;
if (a <= mid && query(ls[u], l, mid, a, b)) return 1;
if (b > mid && query(rs[u], mid + 1, r, a, b)) return 1;
return 0;
}
void dfs(int u)
{
for (int v : g[u])
{
dfs(v);
rt[u] = merge(rt[u], rt[v], 1, V);
}
}
namespace SAM
{
/* 自行完成 */
void insert(char c)
{
int cur = ++cnt;
st[cur].len = st[last].len + 1;
modify(rt[cur], 1, V, st[cur].len);
/* 自行完成 */
}
}
```
（注：本题中的线段树合并需要再 `merge` 函数中新开点，以维护除根节点以外节点的信息不被破坏。）
接着就相对简单了，记 $to_i$ 表示匹配了 $x$ 的 $[0,i)$ 字符，接上一个字符的最小字符。
剩余看代码解释即可。
```cpp
int main()
{
#ifdef ONLINE_JUDGE
FASTIO;
#endif
cin >> s; n = s.size(); SAM::init();
for (int i = 0; i < n; i++) SAM::insert(s[i] - 'a');
for (int i = 1; i <= SAM::cnt; i++) g[SAM::st[i].link].push_back(i);
dfs(0);
cin >> m;
while (m--)
{
int l, r, k; cin >> l >> r >> s; k = s.size();
int i, u = 0, v;
for (i = 0; ; i++)
{
to[i] = -1;
for (int j = (i == k ? 0 : s[i] - 'a' + 1); j < 26; j++) // 枚举接哪个字符
{
v = SAM::st[u].nxt[j];
if (v && query(rt[v], 1, V, l + i, r)) // 如果当前节点存在这样的字符串
{
to[i] = j; break;
}
}
if (i == k) break;
v = SAM::st[u].nxt[s[i]-'a']; // 匹配下一个字符
if (!v || !query(rt[v], 1, V, l + i, r)) break; // 匹配不了了
u = v;
}
while (i >= 0 && to[i] == -1) i--;
if (i < 0) cout << "-1\n";
else
{
for (int j = 0; j < i; j++) cout << s[j];
cout << (char)(to[i] + 'a') << "\n";
}
}
return 0;
}
```
## 总结
SAM 是字符串算法中最通用的一种。
他还有扩展版广义 SAM。
先慢慢理解好 SAM，以应对以后的较难字符串问题吧！