后缀自动机

前言

本文侧重于帮助大家理解后缀自动机的结构，缺少最小性、时间复杂度的证明。

定义

后缀自动机是一个存储字符串所有子串的确定性有限状态自动机。换言之，后缀自动机是一个有向图，其中有一个原点，从原点出发的路径即为字符串中的一个子串。后缀自动机可以看作存储一个字符串所有子串，并尽可能的压缩的 AC 自动机。

endpos

让我们思考如何存下所有子串。首先可以考虑用点表示本质不同的子串，然后用类似于 Trie 的边来表示子串之间的关系，但这样的点数仍然是 \(O(n^2)\) 的（其实这就是后缀 Trie）。但我们能发现，有些子串虽然本质不同，但总是同时出现，比如 abcabc 中的 c、bc、abc，它们的出现位置相似，将这些子串合并为一个点，也就是后缀自动机的核心。

记 \(\text{endpos}(t)\) 为字符串 \(s\) 中，子串 \(t\) 的所有出现位置的右端点的集合，将 \(\text{endpos}\) 相同的子串合并为一个点。让我们思考一下这样会有什么性质。对于一个子串 \(t\)，如果有比它短的子串 \(t'\) 的 \(\text{endpos}\) 和它一样，那么 \(t'\) 一定是 \(t\) 的后缀；反过来，如果 \(t'\) 是 \(t\) 的后缀，除了二者 \(\text{endpos}\) 相同的情况，还会出现 \(\text{endpos}(t) \subset \text{endpos}(t')\) 的情况，因为 \(t'\) 比 \(t\) 少了一些字符，可能出现能够匹配其他位置的情况。因此可以总结出以下性质：

对于 \(\text{endpos}\) 相同的子串，如果按照长度从小到大排列，那么靠前的子串一定是靠后的子串的后缀；
对于 \(\text{endpos}\) 相同的子串，它们的长度能取到其中最大值和最小值之间的所有数；
对于 \(\text{endpos}\) 不同的子串，它们的 \(\text{endpos}\) 要么具有包含关系，要么没有交集。

\(\text{endpos}\) 是后缀自动机压缩结点的依据，虽然我们不需要也不应该将每个结点的 \(\text{endpos}\) 记录下来，但了解这个概念对理解后缀自动机有很大帮助。为了实现压缩的效果，我们需要后缀链接 \(\text{link}\)。

link

由于我们根据 \(\text{endpos}\) 压缩了结点，因此我们可以记结点 \(u\) 对应子串的 \(\text{endpos}\) 为 \(\text{endpos}(u)\)。根据上面的结论，对于 \(\text{endpos}\) 不同的结点，我们可以将其连成一棵树，每条边表示 \(\text{endpos}\) 的包含关系。具体来说，对于一个结点 \(u\)，令 \(t\) 为 \(u\) 对应的子串中长度最短的，那么定义后缀链接 \(\text{link}(u)\)指向最长子串为『仅比 \(t\) 少一个开头字符的后缀』（也是『最长的、不在 \(u\) 中的后缀』）的结点，同时这也是『包含 \(\text{endpos}(u)\) 的、\(\text{endpos}\) 大小最小的结点』。如果不存在这样的结点，那么连到原点（也就是代表空串的结点）。可以发现，\(\text{link}\) 构成了一颗以原点为根的树，这个树被成为后缀链接树，或 Parent 树。

如果记结点 \(u\) 表示的最长子串的长度为 \(\text{len}(u)\)，那么 \(u\) 表示的子串长度的范围为 \([\text{len}(\text{link}(u)) + 1, \text{len}(u)]\)。

\(\text{link}\) 起到类似 AC 自动机中 \(\text{lnkil}\) 的作用，有了它才能快速构建后缀自动机。

如何直观理解这些 \(\text{endpos}\) 和 \(\text{link}\)

假设字符串为 \(\texttt{abcdede}\)，一个结点 \(u\) 表示的最长子串为 \(\texttt{abcde}\)，这个结点子串长度的最小值为 \(3\)，那么这个结点表示的子串为 \(\texttt{abcde}, \texttt{bcde}, \texttt{cde}\)；这个结点的 \(\text{endpos}\) 为这些子串出现位置的右端点。由于这些子串出现的次数和位置都相同，因此被合并到 \(u\)。

对于子串 \(\texttt{de}\)，它的长度为 \(2\)，不在 \(u\) 点中，这是因为它出现位置比 \(\texttt{abcde}\) 要多，\(\text{endpos}\) 不一致。同时，由于 \(\texttt{abcde}\) 的所有长度大于等于 \(3\) 的后缀都被合并到了 \(u\)，\(\texttt{abcde}\) 的最长后缀就是 \(\texttt{de}\)，因此需要将 \(\text{link}(u)\) 设为 \(\texttt{de}\) 对应的结点。

构造算法

后缀自动机使用增量构造的方式进行的。假设当前已经构建出 \(s\) 的后缀自动机，想要添加字符 \(c\)。

首先 \(s + c\) 对应的结点一定要新增，因为 \(s\) 中不存在结束位置为 \(|s| + 1\) 的结点。我们记录上一次插入后，这个字符串本身对应的结点 \(u\)，也就是现在 \(s\) 本身对应的结点，然后将 \(\text{son}(u, c)\) 连接到 \(s + c\) 对应的结点。新增的结点为 \(v\)，\(\text{len}(v)\) 即为 \(\text{len}(u) + 1\)。
接下来，我们需要遍历 \(s\) 所有的后缀，为它们添加到新结点的链接，表示 \(s\) 的后缀添加字符 \(c\) 后的结束位置为 \(|s| + 1\)。这时我们需要将 \(u\) 反复跳转 \(\text{link}\)，如果 \(u\) 当前跳转到的结点不存在 \(\text{son}(u, c)\)，那么将 \(\text{son}(u, c)\) 连接到 \(v\) 上。如果存在 \(\text{son}(u, c)\)，说明之前已经存在一个当前后缀 \(+c\) 的子串了，此时便不能更改，因为这个子串在之前出现过，它的 \(\text{endpos}\) 和 \(v\) 的 \(\text{endpos}\) 不一样（值得一提的是，这个结点的所有子串的 \(\text{endpos}\) 实际上都新增了 \(|s| + 1\)，不过在实现时就不需要处理了）。一个结论是，如果某个跳转过程中的结点 \(u\) 存在 \(\text{son}(u, c)\)，那么 \(u\) 之后跳转的结点都将存在 \(\text{son}(u, c)\)，因为既然这个子串已经存在，其后缀也必然存在。那么，在代码中，只需要跳转到第一个有 \(\text{son}(u, c)\) 的结点即可结束。
接下来需要求出新结点的 \(\text{link}\)。在刚刚连接孩子时，我们会遍历到第一个有 \(\text{son}(u, c)\) 的结点 \(u\)，令 \(x\) 为 \(\text{son}(u, c)\)，\(t\) 为 \(u\) 代表的最长子串，那么 \(x\) 是有可能成为 \(\text{link}(v)\) 的。如果 \(\text{len}(x) = \text{len}(u) + 1\)，说明 \(x\) 表示的子串的最长子串即为 \(t + c\)，正好是最长的不在新结点中的后缀，可以直接将新结点的 \(\text{link}\) 设为 \(x\)；反之，\(\text{len}(x) > \text{len}(u) + 1\)（因为连接孩子是总是将长度长的连到短的上），\(x\) 中存在长度大于 \(|t| + 1\) 的子串，这些子串并不出现在 \(|s| + 1\) 的位置，因此不能直接连接，因此我们需要将 \(x\) 拆成两部分，长度小于等于 \(|t| + 1\) 和长度大于 \(|t| + 1\)，再设置 \(\text{link}\)。
对于需要分裂结点的情况（也可以叫复制或克隆），我们新建结点 \(y\)，表示长度小于等于 \(|t| + 1\) 的子串，原来的结点 \(x\) 表示长度大于 \(|t| + 1\) 的子串，\(y\) 的 \(\text{son}\) 和 \(x\) 相同，\(\text{len}(y) \gets \text{len}(u) + 1\)，\(\text{len}(x)\) 不用改，\(\text{link}(y) \gets \text{link}'(x), \text{link}(x) \gets y, \text{link}(v) \gets y\)。然后继续沿 \(\text{link}\) 遍历 \(u\)（\(u\) 是上文中的第一个存在 \(\text{son}(u, c)\) 的结点），目的是把原先 \(\text{son}(u, c) = x\) 的改为 \(y\)，这是因为新的 \(x\) 只包含长度大于 \(|t| + 1\) 的子串了，和 \(u\) 表示的子串没有交集了，需要改为 \(y\)。同时，这里也有类似 2 中的结论，如果跳转过程中，遇到某个 \(\text{son(u, c)} \ne x\)，后续也不会遇到等于 \(x\) 的情况，所以直接结束。

代码

class SAM {
private:
    static const int M = N * 2;
    int tot, lst, lnk[M], pos[M], len[M], son[M][26];
    bool cln[M];
    vector<int> edg[M];

public:
    SAM() : tot(1), lst(1) {}
    void insert(int c, int p) {
        c -= 'a';
        int u = lst, v = lst = ++tot;
        pos[v] = p, len[v] = len[u] + 1;
        for (; u && !son[u][c]; u = lnk[u])
            son[u][c] = v;
        if (!u)
            lnk[v] = 1;
        else {
            int x = son[u][c];
            if (len[x] == len[u] + 1)
                lnk[v] = x;
            else {
                int y = ++tot;
                lnk[y] = lnk[x], pos[y] = pos[x], len[y] = len[u] + 1, cln[y] = true;
                for (int i = 0; i < 26; ++i)
                    son[y][i] = son[x][i];
                for (lnk[x] = lnk[v] = y; u && son[u][c] == x; u = lnk[u])
                    son[u][c] = y;
            }
        }
    }
    void init() {
        for (int i = 2; i <= tot; ++i)
            edg[lnk[i]].push_back(i);
    }
};

其中，原点为 \(1\) 号结点，初始 lst 和 tot 都被赋值成 \(1\)；cln 变量表示一个结点是否是复制产生的结点。

firstpos

你可能会注意到，上面的代码中有之前未提及的 pos 变量，这正是这一段要说的 \(\text{firstpos}\)。

\(\text{firstpos}(u)\) 为 \(\text{endpos}(u)\) 中，最小的元素，也就是 \(u\) 对应的子串的最早出现位置。对于非克隆结点，也就是第 12 行创建的结点，\(\text{firstpos}\) 为外部传入的 \(p\)，一般来说会传入新增的字符对应的下标。对于克隆结点，其 \(\text{firstpos}\) 就是被复制的结点的 \(\text{firstpos}(u)\)。

关于 \(\text{firstpos}\) 和 \(\text{endpos}\)，有这样的结论：\(\text{endpos}(u) = \displaystyle\bigcup_{v \in \text{subtree}(u)} \{\text{firstpos}(v)\}\)，也就是后缀链接树中，\(u\) 的子树中所有结点 \(\text{firstpos}\) 组成的集合。进一步地，如果只选择子树中的非克隆结点，这些结点的 \(\text{firstpos}\) 互不相同，且恰好构成 \(\text{endpos}(u)\)。这能为后缀自动机的应用打下基础。

复杂度

如果字符串长度为 \(n\)，那么后缀自动机的点数最多为 \(2n - 1\)，边数最多为 \(3n - 4\)。如果用数组存孩子，那么时间和空间复杂度均为 \(O(n |\Sigma|)\)，其中 \(\Sigma\) 为字符集。如果用 map 存，时间复杂度为 \(O(n \log |\Sigma|)\)，空间复杂度为 \(O(n)\)。

应用

本质不同子串个数

给定字符串 \(s\)，求其本质不同的子串个数。

对每个点的 \(\text{len}(u) - \text{len}(\text{link}(u))\) 求和即可。

判断模式串是否出现

给定文本串 \(s\)，模式串 \(t\)，求 \(t\) 是否出现在 \(s\) 中。

先对 \(s\) 构建后缀自动机。从原点出发，沿 \(t\) 的字符进行遍历，如果遇到某个点无法继续遍历，说明 \(s\) 中不含 \(t\)，反之则说明 \(t\) 在 \(s\) 中出现。单次询问的时间复杂度为 \(O(|t|)\)。

找出模式串的所有出现位置

给定文本串 \(s\)，模式串 \(t\)，求出 \(t\) 在 \(s\) 中的所有出现位置。

先判断 \(t\) 是否在 \(s\) 中出现。如果出现，则会找到模式串 \(t\) 对应的结点，这个结点的 \(\text{endpos}\) 即为所有出现的位置。通过遍历子树，统计非克隆结点的 \(\text{firstpos}\) 即可找出所有位置。可以证明 ~~（我不会证明）~~，子树大小是 \(O(|\text{endpos}|)\) 的，因此单次查询的复杂度为 \(O(|t| + |\text{answer}|)\) 的。

求出模式串的出现次数

给定文本串 \(s\)，模式串 \(t\)，求出 \(t\) 在 \(s\) 中的出现次数。

我们只需要求出 \(\text{endpos}\) 的大小即可，因为子树中非克隆结点的 \(\text{firstpos}\) 能不重复地统计出现位置，因此，出现次数即为子树中非克隆结点的个数，可以 dfs 预处理。查询时，直接输出对应结点的统计结果即可。单次询问的时间复杂度为 \(O(|t|)\)。

和 AC 自动机的关系

AC 自动机同样能解决字符串匹配问题。它解决的是『多个模式串的匹配问题』，通过将构建模式串的 AC 自动机，再查询文本串，实现固定模式串、查询文本串的功能。而后缀自动机是构建文本串的后缀自动机，在查询模式串，实现固定文本串、查询模式串的功能。