后缀自动机

· · 算法·理论

SAM 是一个 DAG，每条边上有一个字符。对于一个字符串 s，SAM 上任意一条从起点开始的路径，与 s 的所有子串一一对应。

parent 树

对于一个字符串 s，我们把它的所有前缀倒着插入一颗 Trie。例如 s = "cbaba"，我们构造一颗 c, bc, abc, babc, ababc 的 Trie：

:::align{center}

:::

其实这棵树就符合我们对 SAM 的定义（s 的反串），不过它太大了，它的点数是 \mathcal O(n^2) 级别的。

原因是它是一棵树，因此从起点到任意点的路径只有一条，即树上一个点唯一对应一个子串。而一个串的本质不同子串数量是 \mathcal O(n^2) 级别的，因此复杂度不太对。

考虑建它所有叶子的虚树。即如果一个点只有一个儿子，就把它和他儿子压缩起来：

:::align{center}

:::

这就是真正的 parent 树。根据虚树的性质，这棵树的点数是 \mathcal O(n) 的。

此时一个点可以对应多个多个子串。例如 3 可以对应 aba, abab, ababc 这些 s^R 的子串。反过来就是 aba, baba, cbaba。观察这些子串，它们是从 1 对应的 ba 开始，向前依次加入 a,b,c 后得到的字符串。

定义一个子串 t 的 endpos 为 s 中 t 每次出现时的结束位置的集合。例如 s = "cbaba"，endpos("ba") = {3, 5}。

:::info[结论]{open}

证明略。其实不难感性理解。

还可以这样理解：对于一个前缀 s[1,i]，它对应的 parent 树上的点的 endpos 肯定包含 i。设这个点是 u，那么 u 的父亲对应的子串一定是 s[l,i], s[l+1,i] \dots s[r,i]，显然它的 endpos 一定包含 u 的 endpos（因为你变短了，更有可能在别的地方匹配上）。

:::align{center}

:::

SAM

我们回到 SAM。SAM 的节点就是 parent 树上的点，它也对应一堆 endpos 相同的子串。

每个点最多有 26 个儿子，表示我当前这个点代表的所有子串，添加一个字符后，可以转移到哪个点。一个点的入度可能有多个，因此一个点代表的子串是所有入边的并。

重新强调一下，一个点代表的所有子串，是：

我们考虑如何构造 SAM 和 parent 树。事实上，SAM 中的后缀链接（link）就是 parent 树的树边。

SAM 的构造是在线的。具体而言，我们每次在当前字符串的最后添加一个字符，然后尝试更新整个树和 DAG 的形态。假设我们已经加入了 s[1,i]，现在加入字符 s_{i+1}=c。

我们新建一个点 cur，表示我们即将有一堆之前从未出现过的子串出现，它们是 s[1,i+1],s[2,i+1]\dots s[x, i+1]。再短的 s[x+1,i+1] 已经出现过所以不考虑。我们尝试用 cur 来代表这些点。

设代表 s[1,i] 的点是 lst。显然在 lst 代表的所有子串的最后添加 c 后可以转移到 cur。于是直接 son_{lst,c} \gets cur 即可。

同样的，lst 的父亲一定是某个 s[y,i]，在它后面添加 c 也可以转移到 cur。于是我们暴力跳 lst 的父亲，更新它的 c 出边即可。

但是如果跳到某个祖先 p 时发现 son_{p,c} 已经有值了，设它是 q，那么就代表我们找到 s[x+1,i+1] 对应的点了。

此时最简单的想法是直接将 cur 的父亲设为 q，但如果 q 代表的所有子串中，s[x+1,i+1] 不是最长的，而是存在另一个更长的 s[l,r]，那直接认父亲是不对的。

如何判断 s[x+1,i+1] 是不是最长的？有个很简单的方法是判断 len_q=len_p+1 是否成立。这里 len_u 表示 u 这个节点所代表的最长子串的长度。首先 len_q \ge len_p+1 是一定成立的。进一步如果 len_q > len_p+1，就代表还存在一个更长的子串 s[l,r]，且 s[l,r] 一定不是从 p 转移而来，即 s[l,r] 并不是 s[1,i] 的后缀，所以 s[l,r]+c 也不是 s[1,i+1] 的后缀。那直接接显然是不对的。

所以这里分类讨论。

tr[u].link = tr[q].link;
tr[u].len = tr[p].len + 1;
tr[q].link = tr[cur].link = u;
for (int j = 0; j < 26; ++ j ) tr[u].son[j] = tr[q].son[j];

:::align{center}

情况一 :::

:::align{center}

情况二 :::

红字表示这个节点代表的最长子串的出现位置之一。

注意我们是把 q 在 parent 树的意义下拆成了两个点，因此它在 SAM 上的信息（即出边）应该完全继承 q。

然后我们考虑 p 以及 p 的所有祖先。这些点所代表的子串一定是某个 s[y,i]。如果原来它们的 c 出边指向的是 q，现在应该换成更具体的 u 了。

:::success[构建 SAM 代码]{open}

lst = idx = 1;

struct Node {
    int link, len, son[26];
}tr[N];

void insert(int c) {
    int cur = ++ idx;
    tr[cur].len = tr[lst].len + 1;
    while (lst && !tr[lst].son[c]) {
        tr[lst].son[c] = cur;
        lst = tr[lst].link;
    }

    if (!lst) {
        tr[cur].link = 1;
    } else {
        int p = lst, q = tr[lst].son[c];
        if (tr[q].len == tr[p].len + 1) tr[cur].link = q;
        else {
            int u = ++ idx;
            tr[u].link = tr[q].link, tr[u].len = tr[p].len + 1, tr[q].link = tr[cur].link = u;
            for (int j = 0; j < 26; ++ j ) tr[u].son[j] = tr[q].son[j];
            while (lst && tr[lst].son[c] == q) {
                tr[lst].son[c] = u;
                lst = tr[lst].link;
            }
        }
    }

    lst = cur;
}

:::

总结

我们关心的其实只有这些事情：

例题

:::info[AT_abc433_g Substring Game]{open} 给定一个字符串 s。有一个初始为空的字符串 t，Alice Bob 轮流操作，每次在 t 的最后添加一个小写英文字母，且需要保证新的 t 仍是 s 的某个子串。求两人在绝顶聪明的情况下谁会获胜。 :::

这道题是对 SAM 最浅显的应用。我们把“在 t 最后添加一个字母使得仍是 s 的子串”视作一枚棋子在 DAG 上走了一条出边，所以做法就是 DAG 上 DP，求从每个点出发先手是否存在必胜策略。

:::info[P3804 【模板】后缀自动机（SAM）]{open} 给定一个字符串 s，求 s 的所有出现次数不为 1 的子串的出现次数乘上该子串长度的最大值。 :::

这道题需要我们刻画所有子串的“出现次数”和“长度”。我们知道 SAM 中的一个节点 u 对应一组 endpos 相同的子串，显然只有最长的那个子串可能作为答案，而它的长度正好就是 len_u。如果我们要求它的出现次数，即求 endpos 集合的大小，从 DAG 视角可以是从 1 走到 u 的方案数，从 parent 树视角可以是 u 子树内的关键点数量（关键点就是插入每个前缀 s[1,i] 时对应的 cur 节点）。于是我们做一遍拓扑排序 DP，或者 dfs 求子树和就能得到这个点的 endpos 大小。

:::info[CF1780G Delicious Dessert]{open} 给定一个字符串 s，求有多少子串使得其出现次数能被长度整除。 :::

求一个子串的出现次数仍然是上一题的做法。而一个节点代表的一组子串的长度是不同的。不过这也好办，它们的长度恰好取遍 [len_{link_u} + 1, len_u] 中的所有值。得到这个结论可以想象压缩前的 parent 树。于是我们需要快速求出一个数在一段范围内的约数个数。预处理所有约数后二分即可。

:::info[P2408 不同子串个数]{open} 给定一个字符串 s，求不同的子串的个数。 :::

SAM 上一个节点代表的一组子串是互不相同的。所以答案就是每个点代表的子串个数之和，即 \sum len_u - len_{link_u}。当然也可以拓扑排序 + DP 求从 1 出发的不同路径数量。

:::info[P3181 [HAOI2016] 找相同字符]{open} 给定两个字符串 s,t。求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。 :::

容易将题目转化为 \sum_i \sum_j LCS(s[1,i],t[1,j])，其中 LCS(a,b) 指的是 a,b 的最长公共后缀。

一般求 LCS/LCP 这种问题都是后缀数组的强项，不过在 SAM 的后缀树的视角下会更加直观，尽管这两者是等价的。

对于两个字符串，如果我们能在 SAM 中找到它们对应的节点 u,v，那么这两个字符串的 LCS 就是 u,v 在 parent 树上的 LCA 的 len。这点依旧可以通过想象压缩前的 parent 树得到。

但是现在的两个字符串 s[1,i],t[1,j] 来自两个字符串。我们构造一个新字符串 a = s + c + t，其中 c 是一个不出现 s,t 中的特殊字符，比如 @, $。然后对 a 建 SAM。那么 SAM 上会有若干从 s 来的关键点，和从 t 来的关键点。我们需要求出任意两个不同类的关键点的 LCA 的 len 的和。考虑经典做法，枚举 LCA 然后计算来自不同儿子的两类关键点的数量即可。

:::info[P6640 [BJOI2020] 封印]{open} 给定两个字符串 s,t，q 次询问，每次询问 s[l...r] 和 t 的最长公共子串长度。 :::

求两个字符串的最长公共子串，可以用类似上面的做法，在两个串之间添加特殊字符后建 SAM，然后对于 endpos 中既有 s 中的位置也有 t 中的位置的节点，它的 len 就是答案。

对于本题，首先尝试求出 f_i 表示 s 中以 i 结尾的和 t 的最长公共子串长度。答案即 \max_{i=l}^r \min(f_i,i-l+1)，即枚举 s 中对应最长公共子串的结尾。

注意到如果最终答案是把 f_i 的开头截了一段得到的（即 f_i > i-l+1，此时需要把 l 前面的部分截去），那么这个 i 肯定越大越好。于是线段树二分找到最后一个 i 使得 i-f_i+1 < l，设它是 j。如果答案不是把 f_i 的开头截一段得到的，那么 i<j 的答案肯定不优，而 i>j 一定天然满足 i-f_i+1 \le l，于是直接找 [j+1,r] 中 f 的最大值即可。

现在的问题是如何预处理 f。对 s + c + t 建 SAM，其中 c 是特殊字符。然后如果后缀树上一个节点的 endpos 中，既有 s 中的位置，也有 t 中的位置，就把所有 s 中的位置对应的 f 与这个点的 len 取 \max 即可。

具体的，我们在这个点上打 tag，表示这颗子树内的特殊点的答案都需要与这个 tag 取 \max。最后求一遍祖先最大值即可。

:::info[AT_abc452_g 221 Substring]{open} 定义一个数字串是好的，当且仅当每个极长连续段的长度与这个数相同（即出现恰好 x 个 x）。给定一个数字串 s，求有多少本质不同的好的子串。 :::

依旧从 DAG 上考虑。设 f_{u,i,j} 表示从起点走到 u 且目前已经走过了 j 个 i。转移显然：

\begin{matrix} f_{u,i,j} \to f_{son_{u,i}, i, j + 1} & j<i \\ f_{u,i,j} \to f_{son_{u, k}, k, 1} & j = i, k \ne i \end{matrix}

这个做法比较暴力直接。复杂度 \mathcal O(n |\Sigma|^2)。我们考虑一种更精明的做法。

设在原串中，有一个 x 的极长连续段的长度为 y（即连续出现了 y 个 x）。那么：

考虑将这个段重写：如果 x>y 将其重写成 [-1]，如果 x=y 将其重写成 [x]，如果 x<y 将其重写成 [x,-1,x]。其中 -1 表示必须不能跨过。于是现在的问题是求有多少不包含 -1 的本质不同的子串。建 SAM 后拓扑排序 + DP 即可。具体的设 f_u 表示从 1 走到 u 且中途不走 -1 的方案数。