Liveddd's Blog

愛にできることはまだあるかい

后缀自动机

发表于 更新于 分类于
本文字数： 5.8k 阅读时长 ≈ 13 分钟

强大的，什么都不会的，现在来补的。

0.结构

SAM 是一张有向无环图。结点被称作 状态，边被称作状态间的 转移。
图存在一个源点 $t_0$，称作 初始状态，其它各结点均可从 $t_0$ 出发到达。
每个 转移 都标有一些字母。从一个结点出发的所有转移均 不同。存在一个或多个 终止状态。如果我们从初始状态 $t_0$ 出发，最终转移到了一个终止状态，则路径上的所有转移连接起来一定是字符串 $s$ 的一个后缀。$s$ 的每个后缀均可用一条从 $t_0$ 到某个终止状态的路径构成。在所有满足上述条件的自动机中，SAM 的结点数是最少的。

直观上，字符串的 SAM 可以理解为给定字符串的所有子串的压缩形式。值得注意的事实是，SAM 将所有的这些信息以高度压缩的形式储存。对于一个长度为 $n$ 的字符串，它的空间复杂度为 $O(n)$。构造 SAM 的时间复杂度仅为 $O(n)$。并且一个 SAM 最多有 $2n-1$ 个节点和 $3n-4$ 条转移边。

SAM 最简单、也最重要的性质是，它包含关于字符串 $s$ 的所有子串的信息。任意从初始状态 $t_0$ 开始的路径，如果我们将转移路径上的标号写下来，都会形成 $s$ 的一个子串。

1.构造

先介绍一些线性构造 SAM 的关键。

1.1 结束位置 endpos

对于 $s$ 的任意非空字串 $t$ 的，我们记 $\operatorname{endpos}(t)$ 为 $t$ 在 $s$ 中所有出现位置的集合。

若 $\operatorname{endpos}(t_1)=\text{endpos}(t_2)$，我们则称 $t_1,t_2$ 属于同一个等价类。而 SAM 中的每个状态就对应着所有等价类。并且我们容易得到以下几条引理：

引理 1： 字符串 $s$ 的两个非空子串 $u$ 和 $w$（假设 $\left|u\right|\le \left|w\right|$）的 $\operatorname{endpos}$ 相同，当且仅当字符串 $u$ 在 $s$ 中的每次出现，都是以 $w$ 后缀的形式存在的。

引理 2： 考虑两个非空子串 $u$ 和 $w$（假设 $\left|u\right|\le \left|w\right|$）。那么要么 $\operatorname{endpos}(u)\cap \operatorname{endpos}(w)=\varnothing$，要么 $\operatorname{endpos}(w)\subseteq \operatorname{endpos}(u)$，取决于 $u$ 是否为 $w$ 的一个后缀。

引理 3： 考虑一个 $\operatorname{endpos}$ 等价类，将类中的所有子串按长度非递增的顺序排序。每个子串都不会比它前一个子串长，与此同时每个子串也是它前一个子串的后缀。换句话说，对于同一等价类的任一两子串，较短者为较长者的后缀，且该等价类中的子串长度恰好覆盖整个区间 $[x,y]$。

对于状态 $v$ 所代表的等价类，我们设其中最长的子串为 $w$，等价类中其余子串均为 $w$ 的后缀。$\operatorname{link}(v)$ 连接到 $w$ 的最长后缀的对应的另一个等价类上。

容易发现， 所有后缀链接构成一棵根节点为 $t_0$ 的树。并且，通过 $\operatorname{endpos}$ 集合构造的树（每个子节点的 $\textit{subset}$ 都包含在父节点的 $\textit{subset}$ 中）与通过后缀链接 $\operatorname{link}$ 构造的树相同。这棵树我们称之为 parent 树。

那么线性状态数就好理解了，我们视作不断将 父亲节点对应的集合 分裂成若干个 儿子节点对应的子集，这些子集或不相交。这样显然最多分 $n-1$ 次，最终最多剩 $n$ 个节点，所以等价类个数即状态个数最多有 $2n-1$ 个。

1.3 过程

  • 令 $\textit{last}$ 为添加原串第 $i$ 个字符 $c$ 之前，整个字符串对应的状态（一开始我们设 $\textit{last}=0$，算法的最后一步更新 $\textit{last}$）。

  • 创建一个新的状态 $\textit{cur}$，并将 $\operatorname{len}(\textit{cur})$ 赋值为 $\operatorname{len}(\textit{last})+1$，在这时 $\operatorname{link}(\textit{cur})$ 的值还未知。

    ——此时 $\textit{cur}$ 对应着一个全新的等价类，就代表着 当前已加入的字符串，$\operatorname{endpos}(\textit{cur})$ 为 ${i}$。

  • 现在我们按以下流程进行（从状态 $\textit{last}$ 开始）。如果还没有到字符 $c$ 的转移，我们就添加一个到状态 $\textit{cur}$ 的转移，遍历后缀链接。如果在某个点已经存在到字符 $c$ 的转移，我们就停下来，并将这个状态标记为 $p$。

  • 如果没有找到这样的状态 $p$，我们就到达了虚拟状态 $-1$，我们将 $\operatorname{link}(\textit{cur})$ 赋值为 $0$ 并退出。

  • 假设现在我们找到了一个状态 $p$，其可以通过字符 $c$ 转移。我们将转移到的状态标记为 $q$。

    ——相当于我们不断在 $last$ 对应的后缀中找等价类，并且添加转移边。如果找到一个存在该转移边的状态，那么显然当前等价类 $\textit{cur}$ 的 $\operatorname{endpos}(\textit{cur})$ 的 超集 在之前就已经出现过。我们需要进一步讨论。

  • 现在我们分类讨论两种状态，要么 $\operatorname{len}(p) + 1 = \operatorname{len}(q)$，要么不是。

  • 如果 $\operatorname{len}(p)+1=\operatorname{len}(q)$，我们只要将 $\operatorname{link}(\textit{cur})$ 赋值为 $q$ 并退出。

    ——这里显然 $\textit{cur}$ 的父亲节点是 $q$。

  • 否则就会有些复杂。需要 复制 状态 $q$：我们创建一个新的状态 $\textit{clone}$，复制 $q$ 的除了 $\operatorname{len}$ 的值以外的所有信息（后缀链接和转移）。我们将 $\operatorname{len}(\textit{clone})$ 赋值为 $\operatorname{len}(p)+1$。

    复制之后，我们将后缀链接从 $\textit{cur}$ 指向 $\textit{clone}$，也从 $q$ 指向 $\textit{clone}$。

    最终我们需要使用后缀链接从状态 $p$ 往回走，只要存在一条通过 $p$ 到状态 $q$ 的转移，就将该转移重定向到状态 $\textit{clone}$。

    ——这意味着，$q$ 等价类中还存在其它更大的子串。于是我们需要分裂等价类，需要将 $q$ 重新分裂为 $\textit{clone},q’$ 两个等价类，其中 $\operatorname{len}(\textit{clone})=\operatorname{len}(p)+1$。

  • 以上三种情况，在完成这个过程之后，我们将 $\textit{last}$ 的值更新为状态 $\textit{cur}$。

理解以上过程就会感觉很清晰很正确！我们可以证明上述构造过程操作数是线性的，不过证明此处略去。最终我们在 $\mathcal O(n)$ 的时间复杂度以内完成对 SAM 构造。代码比较简洁。

1.4 实现

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
namespace SAM
{
    struct Node{int fa,len,ne[C];}g[N<<1];
    int tot=1,last=1;
    void insert(int c)
    {
        int p=last,x=last=++tot;
        g[x].len=g[p].len+1;
        while(p&&!g[p].ne[c])
            g[p].ne[c]=x,p=g[p].fa;
        if(!p)return g[x].fa=1,void();
        int q=g[p].ne[c];
        if(g[q].len==g[p].len+1)return g[x].fa=q,void();
        int nq=++tot;
        g[nq]=g[q],g[nq].len=g[p].len+1,g[x].fa=g[q].fa=nq;
        while(p&&g[p].ne[c]==q)
            g[p].ne[c]=nq,p=g[p].fa;
    }
};

2.应用

2.1 检查字符串是否出现

给一个文本串 $T$ 和多个模式串 $P$，我们要检查字符串 $P$ 是否作为 $T$ 的一个子串出现。

我们直接在 SAM 跑即可，时间复杂度 $\mathcal O(|P|)$。

2.2 不同子串个数

给一个字符串 $S$，计算不同子串的个数。

每个 $S$ 的子串都相当于自动机中的一些路径。因此不同子串的个数等于自动机中以 $t_0$ 为起点的不同路径的条数。简单 DP 求解即可。

那如果我们要动态维护，即查询每个前缀的答案？我们每次考虑当前新增的等价类 $i$。因为 SAM 上等价类对应着一段长度为连续区间的后缀，所以新增的未出现的子串就是 $\operatorname{len}(i)-\operatorname{len}(\operatorname{link}(i))$，对其求和即可。

二者时间复杂度均为 $\mathcal O(|S|)$。

2.3 所有不同子串的总长度

给定一个字符串 $S$，计算所有不同子串的总长度。

与 2.2 相当类似，我们可以使用 DP 直接求解。也可以考虑新增的等价类 $i$，那么就是一个等差数列求和了。

二者时间复杂度均为 $\mathcal O(|S|)$。

2.4 字典序第 $k$ 大子串

先一遍简单 DP 求出后继状态的路径数。再 DFS 直接找就行了。单词查询时间复杂度 $\mathcal O(|ans|\cdot |\Sigma|)$，$|ans|$ 为答案长度。

2.5 最小循环移位

给定一个字符串 $S$。找出字典序最小的循环移位。

容易发现字符串 $S+S$ 包含字符串 $S$ 的所有循环移位作为子串。

所以问题简化为在 $S+S$ 对应的后缀自动机上寻找最小的长度为 $\left|S\right|$ 的路径。我们从初始状态开始，贪心地访问最小的字符即可，时间复杂度为 $\mathcal O(\left|S\right|)$。

用最小表示法也可以简单做到 $\mathcal O(\left|S\right|)$。

2.6 出现次数

对于一个给定的文本串 $T$，有多组询问，每组询问给一个模式串 $P$，回答模式串 $P$ 在字符串 $T$ 中作为子串出现了多少次。

利用 parent 树，DFS 求出每个节点的终点集合的大小。再把 $P$ 放在 PAM 上跑，输出终点集合的大小即可。时间复杂度 $\mathcal O(|T|+\sum|P|)$。

2.7 第一次出现的位置

与 2.6 类似，不过求出每个节点的终点集合最靠前的位置即可。其实这个过程中也可在 动态建 SAM 的过程中维护。

2.8 所有出现的位置

与 2.6 类似，遍历 parent 树上所有重点集合即可。

2.9 最短的没有出现的字符串

容易考虑 DP，我们假设所有原本不存在的转移边 连向 $t_1$，我们相当于找一条从 $t_0\to t_1$ 最短的路径，简单 DP 即可。时间复杂度 $\mathcal O(|S|)$。

2.10 两个字符串的最长公共子串

给定两个字符串 $S$ 和 $T$，求出最长公共子串，公共子串定义为在 $S$ 和 $T$ 中都作为子串出现过的字符串 $X$。

先建出 $S$ 的 SAM，考虑 $T$ 的子串在 SAM 上的情况。直接在 SAM 跑，设当前最长公共子串在 SAM 上状态为 $u$，其长度为 $l$。考虑下一位 $T_i$ 的转移是否存在：

  1. 存在转移 $(u,v,T_i)$，那么 $u\to v$，$l\to l+1$。
  2. 不存在转移 $(u,v,T_i)$，那么状态 $u\to \operatorname{link}(u)$，$l\to \operatorname{len}(link(u))$。重新考虑下一位 $T_i$ 的转移是否存在。

显然每次 $l$ 的变化量为 $\mathcal O(|T|)$，最终哦我们取最大值即可，所以总的时间复杂度为 $\mathcal O(|S|+|T|)$。

2.11 多个字符串间的最长公共子串

给定 $k$ 个字符串 $S_i$。我们需要找到它们的最长公共子串，即作为子串出现在每个字符串中的字符串 $X$。

一个单纯的想法是，我们选取一个最短的字符串 $S_i$ 建 SAM，对于其余字符串，都采用与 2.10 类似的方式进行处理。不过不同的是，我们将这些状态 $u$ 直接在 parent 树上标记，并记录最长匹配长度。再在 parent 树上求子树 max。最终对于每个状态，每个串在该状态上最长匹配长度取 min，最终再取最大值即可得到答案。

最终时间复杂度就是 $\mathcal O(\sum|S|)$。