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

· · 题解

SAM 学习笔记

简介：

SAM 是一个用于维护子段信息的自动机。

当然，你也可以把它看成是一个插入了所有后缀的 trie。

铺垫：

我们定义 endpos(s) 下简称 ed(s) 是一个从字符串到集合的函数。

字符串 s 在文本串 T 中作为子串出现的所有位置的结尾位置构成的集合被称为 ed(s)。

给个例子：令文本串 T = \text{ababba}：

其他先不列出来了，我们观察一下这个有什么规律吧。

  1. 如果一个字符串 s 是一个字符串 t 的后缀， 那么有 ed(s) \supseteq ed(t)。

    口头证明一下：每一次字符串 t 出现，那么 s 一定出现，但是 s 可能有出现了但是 t 没有完全出现的情况，所以成立。

  2. 如果 ed(s) \supsetneq ed(t)，那么字符串 s 是一个字符串 t 的后缀。

    其实几乎是 命题1 的逆命题，如果每一次 t 出现都一定有对应 s 的出现，那么显然就一定是后缀。

  3. 要么有 ed(s) \supseteq ed(t) 或 ed(s) \supseteq ed(t)，要么有 ed(t) \cap ed(p) = \varnothing.

    考虑反证：假设现在有交集，那么对于一个共同元素 p，考虑以 p 结尾的所有串互为前后缀关系，由 命题1 即可知道一定存在包含关系。

  4. 对于若干个 s_i，若其 ed(s_i) 相等，那么其长度构成一个连续的区间。

    考虑证明：首先它们互为后缀关系，那么假设第一次让 ed(p) 扩大的点 k，当 k' \ge k+，显然不会回退，得证。

引入：

我们考虑我们想要把所有后缀插入到一个字典树中：

注意到：这些后缀的相同前缀我们已经通过字典树的结构来合并了，那么相同后缀怎么解决呢？

由这个 命题1 想到我们可以通过 ed(p) 来合并后缀。

现在看到我们的 ed(p)，我们突然发现：本质不同的 ed(p) 只有 O(n) 个。

证明： 由 命题3 得知，从空集开始，每一次增加都必然减少一个块，所以是 n 个。

那么我们考虑转移是什么？

首先我们想到的是像字典树的 next 一样的，从一个 ed(p) = S 通过加入一个字符 c 来走到的下一个节点。

然后我们考虑这个不仅仅是一个 trie，还具备子串匹配功能：那么我们需要维护一个像 AC自动机 的 fail 一样的东西，在这里我们叫他 link。

我们观察 AC自动机 的 fail 功能是什么？

我们直接 copy 过来，然后简单修改一下：

根据 命题4 ：每个节点都一定对应一段长度连续的后缀。

那么我们取出其中最长的一个串作为代表：

link 表示 SAM 上与当前节点的代表字符串具有相同后缀的最长代表字符串对应节点。

那么我们的结构就出来了：

如图就是字符串 \text{ababba} 的 next 的构造：

link 的构造：

构建

观察一下这个图片，我们总结一点规律：

那么我们的构建就讲完了：过程比较复杂，大家可以对着图片多手算几次。

实现

void add (int c) {
    int now = np(), p;

    t[now].len = t[lst].len + 1;

    for (p = lst ; ~p && !t[p][c] ; p = t[p].lnk)
        t[p][c] = now;

    if (p == -1) t[now].lnk = 0;
    else {
        int pre = t[p][c];
        if (t[pre].len == t[p].len + 1) t[now].lnk = pre;
        else {
            int ppre = np (pre);
            t[ppre].len = t[p].len + 1;
            t[pre].lnk = t[now].lnk = ppre;

            for ( ; ~p && t[p][c] == pre ; p = t[p].lnk)
                t[p][c] = ppre;
        }
    }

    ans += t[now].len - t[t[now].lnk].len;
    lst = now;
}

应用