字符串仙术——浅谈SAM及应用

凤年 · 2023-05-18 16:22:00 · 个人记录

引入

多模匹配问题可以使用 AC自动机 求解（其实就是预处理了所有模式串），但大多数时候我们并不知道模式串都有什么，所以只能预处理文本串。

给你一个文本串 T 和 n 个模式串 P_{1 \sim n}，请你分别判断模式串 P_i 是否在 T 中出现。

一个简单的例子:

T: abcba
S: ab
   abb
   aab

SAM 满足三条性质：

1. 是一个（DAG）有向无环图
2. 接受且仅接受该串的所有后缀

如果仅有这两条性质，显然一个 后缀trie 就可以满足。

这颗 trie 有这样的性质：

• 从源点到任意节点都表示原串的一个子串
• 从源点到一个终止节点表示原串的一个后缀
• 从源点出发任意两条不同路径都表示不同的子串

如果只有这两个性质，显然是不够的优秀的，因为建树的复杂度就可以达到恐怖的 O(n^2)。所以这里引入 SAM 的第三条性质：

3. 节点尽可能少

观察这颗树可以发现有很多节点是可以合并的，比如：

它可以这样合并：

阴影表示删除部分，红色表示新加转移边

另一部分就不画了。

endpos与等价类

已经弄明白了后缀自动机的性质，那么我们现在就要构造一个点数尽可能少的 DAG 。

定义

定义 \text{endpos}(p) 表示子串 p 在原串 s 中出现的位置，如在 aabab 中 \text{endpos}("ab") = \{3， 5\} ，如果 p1 与 p2 的 endpos 相等我们就称这两个串属于一个等价类（如 \text{endpos}("b") = \text{endpos}("ab") = \{3， 5\}，b 和 ab 属于一个等价类）

endpos等价类的性质

性质1：若两个串的 endpos 相同， 则短串必然是长串的后缀

这个挺明显的吧。

性质2：如果 p1 是 p2 的后缀，则必然有 \text{endpos}(p2) \subseteq \text{endpos}(p1)\

\qquad\;\;\,\,$若不是后缀，则一定有 $\text{endpos}(p1) \bigcap \text{endpos}(p2) = \emptyset

该性质是性质1的逆命题，根据 p1 和 p2 是否是后缀关系来分类讨论。

性质3：将一个等价类中所有串降序排序，每个串的长度都是上一个串长度减1，且是上一个串的后缀。

性质3算是以上两个性质的推论，举个栗子：

根据性质4， 在一个类中最长串的前面加字符会将一个类分割成多个不相交的类， 那么这个新串肯定是新类的最短串，因为在它的前面继续加字符还是在这个新类中。

性质6：后缀自动机的边数最多有 3n-4 条（在形如 abbbb...bc 的串取上界），即 O(n)。

证明割了，想看可以去看 clj 的 ppt。

那么这棵树有什么用呢，直接一点，这棵树上每个节点都与后缀自动机的状态一一对应不过只是多了一点复杂些的转移边而已。

构造SAM

如果仅仅使用母树还不够用，因为每个节点都需要存储这个类的所有子串（真麻烦），但是如果把表示父子关系的箭头去掉，再进行亿点点奇奇怪怪的转移，他就成为了一个非常神奇的结构—— SAM，其实为什么 SAM 这么神呢，因为他并不是存储子串而是使用路径（转移边）表示每一个子串（参考右图）。

仔细想想，字符串算法都有一个通性， 很多算法都是利用已经求出的部分和需要求的内容的性质进而推出剩下的部分， 比如 已经学过的KMP, Hash, Manacher, 现在讲的SAM甚至未来的PAM, exKMP等等等等都是这样求出来的， 理解字符串算法的这个通性有利于考场对字符串题目的求解（敲黑板）。

SAM 使用在线构造， 即一个一个插入字符，然后在之前构建出的 SAM 上进而推出新的的 SAM。

代码先贴这：

int tot = 1/*当前节点总数*/, last = 1/*上一个节点*/;
struct SAM {
    int fa, len, nex[26];
}sam[N << 1];
void add(int x) {
        int now = ++tot, p = last;
        sam[now].len = sam[p].len + 1;
        for(;p && !sam[p].nex[x]; p = sam[p].fa) sam[p].nex[x] = now;

        if(!p) sam[now].fa = 1;
        else {
            int q = sam[p].nex[x];
            if(sam[q].len == sam[p].len + 1)    sam[now].fa = q;
            else{
                int tmp = ++tot;
                sam[tmp] = sam[q];
                sam[now].fa = sam[q].fa = tmp;
                sam[tmp].len = sam[p].len + 1;
                for(; p && sam[p].nex[x] == q; p = sam[p].fa) sam[p].nex[x] = tmp;//让p类的所有祖先都向新扣下来的节点转移
            }
        }
        last = now;
}

int main() {
    ...
    for(int i = 0;i < len; ++i) add(s[i] - 'a');
    ...
}

情况不是很多，也就三种，now 是新更新的类，指针p指向上一个类，初始化时令sam[now].len = sam[p].len + 1 因为现在原串（p代表的串）加上了新字符以后整个串肯定没在原来的母树上出现过 （废话） ，所以新建了一个类，这个类的 longest 是从 p 的 longest 推过来的。

以下称新字符为 ch。

for(;p && !sam[p].nex[x];p = sam[p].fa) sam[p].nex[x] = now: 在 p 的基础上加上一个字符以后只会对原串的所有后缀的 endpos 产生影响，根据母树定义，父子之间以及一个类的子串之间都是后缀包含关系，加上 ch 就相当于让 p 及其祖先都进行了一次 ch 的转移，现在顺着每个节点跳 fa 就可以看成 遍历 longest(p) 的所有后缀串（其实是压缩遍历），直到找到一个曾经接受过 ch 的状态，同时让这条路径上每一个类都向 now 进行转移（毕竟加了 ch, p 这个类上的串以及他的所有祖先（ p 的子串）就都可以向 now 转移）

循环条件 p为真 是防止跳出根节点。

Case 1:

if(!p) sam[now].fa = 1;

当循环结束时如果 p 为假则说明跳到了根，这个情况只有在加入了并未在前面出现的新字符时才会出现，因为没有任何一个状态接受过 ch，这是它的祖先只能是1，所以令 \text{fa}(now) = 1

以下解释是 abcbc 。

加入一个 a 以后长这样（虚线表示父亲，黑线表示转移边，下划线表示这个类的串）

加入一个 b，新建3节点， p指针顺着2跳到了根节点同时让2向3转移，跳到了根节点，说明 b 是个新字符，从根节点向3转移一次，同时让 \text{fa}(2) = 1）

情况同上，不再赘述。

Case 2:

int q = sam[p].nex[x];
if(sam[q].len == sam[p].len + 1)    sam[now].fa = q;

如果循环结束时 p 找到了一个曾接受 ch 的祖先， 则设一个 q 为 p 向 ch 转移后的状态，然后判断 \text{len}(q) 是否等于 \text{len}(p) + 1，又因为q.nex[ch] == q，所以这句话就等价于判断 \text{longest}(q) 是否等于 \text{longest}(p) + ch ，如果\text{longest}(q) = \text{longest}(p) + ch 则说明 q 的所有串都是新串的后缀（p是原串的后缀，加入ch就是新串的后缀，既然\text{logest}(q) 是新串的后缀，则说明整个类都是新串的后缀），所以令 \text{fa}(now) = q，如果不等于就进入下一个情况。

Case 3:

int tmp = ++tot;
sam[tmp] = sam[q];
sam[now].fa = sam[q].fa = tmp;
sam[tmp].len = sam[p].len + 1;
for(; p && sam[p].nex[x] == q; p = sam[p].fa) sam[p].nex[x] = tmp;

这个情况说明找到的 q 的 \text{longest} 并不是 \text{longest}(p)+ch，说明q 这个类至少有一个串不是新串的后缀，这时候我们说 q 是 p 的一个不连续转移（不理解可以看下面的图），因为加入一个字符以后原来是一个类的串现在可能不再是一个类，此时我们复制一个类 tmp 来拿走这个错误的转移扣下来（即让 tmp 再进行一次转移然后才能到 q），我们分别考虑 tmp 的每个信息。

首先考虑 fa 和 len，可以抽象理解为原本是 p \rightarrow q，现在他们之间插入了一个 tmp，变成了 p \rightarrow tmp \rightarrow q，所以 \text{fa}(tmp) = p, \text{len}(q) = \text{len}(p) + 1

现在考虑转移边，由于 tmp 是从 q 扣下来的，所以直接使用 q 的所有转移边，为什么这样做是正确的呢，原本 q 中的串是都可以进行某一些转移的，即使把一部分串抠出来，这部分串仍然可以进行这样的转移，所以我们直接把 q 的所有转移边 copy 过来给 tmp 就行了。由于现在原本 q 中的一部分串给了 tmp，原本这些串是一个等价类里的，所以是符合等价类规律的，即一个类中的短串是长串的后缀，故 \text{fa}(q) = tmp

扯了一大堆，只说了一个 tmp，现在我们回到 now （一开始不是只在考虑怎么找到 now 的 father 吗啊喂 \ (╯‵□′)╯︵┻━┻）

现在 \text{len}(tmp) = \text{len}(p) + 1，他又回到了Case2中的情况，直接 \text{fa}(now) = tmp 就完了。

还有最后一个循环，tmp 继承了 q 的所有转移边以后还有一些边是向 q 转移的，这咋整，现在 \text{fa}(tmp) = q 但是一直让跳 q 的祖先让所有祖先都是向其转移即可。

看一下图片讲解：

可以看到加入5节点后ab和b不再是一个等价类，但是却还保存在节点3中，我们把较短的部分扣下来存进新建的6号节点，令 \text{fa}(3) = 6，6替代了原本3的位置所以让\text{fa}(6) = 1，把原来3的转移边复制给6，\text{fa}(5) = 6，让1及其所有祖先都向6进行 b的转移。

最后别忘了更新 last = now，以便下一次加入新的字符。

整个过程实际上就是在维护一颗后缀树和母树（转移边组成了后缀树，fa边组成了母树），只不过在维护的过程中用到了一些技巧，将时间复杂度从 O(n^2) 降到了 O(n)。

常见的操作

还有一些对于SAM常见的操作，比如重建母树：

void BuildGraph() {//枚举每个节点然后把他的父亲向他连边
        for(int i = 2; i <= tot; ++i) add(v[i].fa, i);
    }
void dfs(int now) {//遍历母树（在一些利用SAM树形结构的DP题中会用到）
        for(int i = head[now]; i; i = e[i].nex) {
            int to = e[i].to;
            dfs(to);
            // siz[now] = siz[now] + siz[to];
            // 用于统计endpos大小
        }
    }

再比如拓扑排序，在利用SAM的DAG性质的时候会用到。可以使用一般的拓扑排序对整个图进行排序，代码就不放了。但是在利用每个节点都有自己的len，且 len 越大越会处于整个图的下部（请允许我这么说因为我找不到更好的形容词了），利用这个性质对其进行基数排序，然后获得拓扑序。

int cnt[N]/*计数器*/, order[N << 1]/*拓扑序为i的节点的编号*/;
void toposort(int n) {
    for(int i = 1;i <= tot; ++i) ++cnt[sam[i].len], mn[i] = sam[i].len;
    for(int i = 1;i <= n; ++i) cnt[i] += cnt[i - 1];
    for(int i = 1;i <= tot; ++i) order[cnt[sam[i].len]--] = i;
}

这样就能获得一个倒拓扑序，使用的时候倒序枚举即可。

这个数据是上面的 abcbc，建完SAM是长这样：

可以对照一下看看拓扑序对不对。

应用

P3804 【模板】后缀自动机（SAM）

给定一个只包含小写字母的字符串 S。 请你求出 S 的所有出现次数不为 1 的子串的出现次数乘上该子串长度的最大值。

用 siz_u 表示节点 u 的节点大小，重建母树然后搜索，统计每个节点的 siz 然后乘上该节点的 len 取 max 即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;

string s;
int head[N << 1];
long long siz[N << 1];
struct edge {
    int nex, to;
} e[N << 1];
void add(int u, int v) {
    static int tot = 0;
    e[++tot].to = v;
    e[tot].nex = head[u];
    head[u] = tot;
}
int tot = 1, last = 1;
struct SAM {
    int fa, len, nex[26];
} sam[N << 1];
void insert(int x) {
    int now = ++tot, p = last;
    siz[now] = 1;
    sam[now].len = sam[last].len + 1;
    for(; p && !sam[p].nex[x]; p = sam[p].fa)
        sam[p].nex[x] = now;
    if(!p)
        sam[now].fa = 1;
    else {
        int q = sam[p].nex[x];
        if(sam[q].len == sam[p].len + 1) sam[now].fa = q;
        else {
            int tmp = ++tot;
            sam[tmp] = sam[q];
            sam[now].fa = sam[q].fa = tmp;
            sam[tmp].len = sam[p].len + 1;
            for(; p && sam[p].nex[x] == q; p = sam[p].fa) sam[p].nex[x] = tmp;
        }
    }
    last = now;
}
void dfs(int now) {
    for(int i = head[now]; i; i = e[i].nex) {
        int to = e[i].to;
        dfs(to);
        siz[now] = siz[now] + siz[to];
    }
}
void find() {
    long long ans = 0;
    for(int i = 1;i <= tot; ++i)
        if(siz[i] != 1)
            ans = max(siz[i] * sam[i].len, ans);
    printf("%lld", ans);
}
int main() {
    cin >> s;
    for(int i = 0, len = s.size(); i < len; ++i) insert(s[i] - 'a');
    for(int i = 2; i <= tot; ++i) add(sam[i].fa, i);
    dfs(1);
    find();
    return 0;
}

P3809 【模板】后缀排序

输出每个后缀串按字典序升序排序后的排名

没错SAM还能求SA，根据定义， 跑完 SAM 以后节点与节点之间的 fa 能构成一颗 parent\ tree， 这棵树上叶子节点的 longest 就是原串的前缀串，所以只要建好 SAM 后按字典序重建母树，然后从根节点往下深搜到达每一个叶子节点即可......个屁啊，事实证明对SAM最大的制约就是空间，这题空间太小了，如果你愿意的话可以参考题解区大佬的挂链哈希SAM。

P2408 不同子串个数

求给定的字符串的本质不同子串个数（即两个子串相同但处于不同位置算作一个子串）

考虑DP，SAM上每一段路径都是一个子串，设 f_v 为节点 v 开始的路径数，可得如下方程：

最后输出 f_1 - 1 即可，因为要跑出空串。

时间复杂度 O(|S|)。

long long dfs(int now) {
    if(ans[now]) return ans[now];
    for(int i = 0;i < 26; ++i)
        if(sam[now].nex[i])
            ans[now] += dfs(sam[now].nex[i]) + 1;
    return ans[now];
}
int main() {
    scanf("%d\n", &n);
    for(int i = 1;i <= n; ++i) add(getchar() - 'a');
    printf("%lld", dfs(1));
    return 0;
}

P4070 [SDOI2016]生成魔咒

同样是求本质不同子串，但是强制在线，每加入一个字符求一次本质不同子串，DP显然不能满足复杂度要求，利用SAM的树形结构，每个节点的子串数量都是 \text{len}(i) - \text{len}(\text{fa}(1))，这样即可实现在线。

只需要在SAM的构造函数末尾加入ans += sam[now].len - sam[sam[now].fa].len即可，还有一点需要注意，本题字符集过大，所以将int nex[26] 数组换成 map<int, int>nex,复杂度加上了一个 \text{log}

P1368 【模板】最小表示法

输出字典序最小的循环同构

建立 S + S 的后缀自动机，从根节点往下贪心地每次选取字典序最小的节点走 |S| 步即可。

for(int i = 1, p = 1;i <= n;++i ) {//往下走n步
    auto it = sam[p].nex.begin();//遍历每一个点的出边
    p = it -> second;//second 指向节点
    printf("%d ", it -> first);//first表示边上的值;
}

P3975 [TJOI2015]弦论

$t = 1$ 求所有子串中的第 $k$ 小子串

还是 siz_i 表示 endpos_i 的大小。