后缀自动机

看了一篇博文，写得很好，让我这个大人机弄明白了 SAM 是什么。

参见

SAM 的定义 ​

SAM，后缀自动机。储存了一个字符串的后缀信息。

1. SAM 是一张 DAG，节点称为 状态，边称为 转移。

2. DAG 有一个 初始状态（节点） $P$，其余所有状态（节点）可以通过一些转移（边）到达。

3. 每一个转移（边）标记 了字符集中的一个字母（边权）。从一个状态（节点）出发的所有边（转移）互不相同。

4. 将从初始状态（节点）到一个 终止状态（节点）经过的所有转移（边）上的标记连接起来，就能得到原串的一个后缀。反之，原串的 任意 一个后缀可以被表示为从初始状态（节点）到某一个终止状态（节点）的路径。

5. 在满足上述条件的 DAG 中，SAM 所使用的节点数最少，为 $O(n)$ 级别，其中 $n$ 是原串长度。（最小性）

正是因为最小性，才能满足我们日益增长的效率需要。所以我们要研究这个 SAM，来使得人机能通过 图灵测试 字符串毒瘤题。

注意到原串的后缀的前缀对应了原串的子串，从起始节点走到终止节点，表示一个后缀，而这条路径上除起点以外任意一个节点都表示原串的一个非空子串。不难发现，由于 SAM 能表示任意后缀，任意子串也能被 SAM 表示，这样 $O(n)$ 个节点压缩了许多信息。

后缀链接 ​

后缀链接通过连接 SAM 中的节点，形成了一棵树的结构。

结束位置与等价类 ​

约定字符串下标从 $1$ 开始。

假设字符串 $S$ 有子串 $s$，定义 endpos(s) 表示 $s$ 在 $S$ 中，每一次出现的 结束位置，组成的集合。由于 $s$ 是一个子串，则 endpos(s) 必定非空。

S="abab"
        s =  "a"  "b","ab"  "aba","ba"  "abab","bab"
endpos(s) = {1,3}  {2,4}        {3}          {4}

上面是一个例子。

显然，两个子串的 $\text{endpos}$ 可能相同，如果两个子串 $\text{endpos}$ 集合相同，称这两个子串处于同一个 等价类 中。

注意 $\text{endpos}$ 是数集，是结束位置下标集合。等价类是字符串集合。

SAM 上的一个节点对应一个等价类。

引理 ​

画画图感受一下，这些都是对的。

1. 两个子串 $\text{endpos}$ 集合相同，等价于，一个子串是另一个子串的后缀 并且 较短串只作为较长串的后缀出现。

2. 若 $s_1$ 是 $s_2$ 的后缀，且 $s_1$ 较长。则较短串 $\text{endpos}$ 集合包含（不一定真包含）较长串的 $\text{endpos}$。否则，两集合交集为空。

   是后缀时，较长串出现时，较短串必然出现，较短串出现时较长串不一定出现。

   不是后缀时，假设存在两集合交集非空，取交集中任一位置，则两个串均以这个位置为结尾出现过，则较短串必定是较长串的后缀，与假设矛盾。

3. 一个 $\text{endpos}$ 集合不包括两个等长但是本质不同的子串。

   如果等长，出现位置又完全一样，难道有可能本质不同吗？

4. 一个等价类中，任意两个串，较短者为较长者的后缀。

   由引理 1 可以得到。有了这个引理，一个等价类中，其余串均是最长串的后缀。

5. 若一个等价类中最短字符串为 $l$，最长字符串为 $r$，则 $[l,r]$ 之间的长度均在该等价类中出现过。

   可以反证，假如有一个长度没有出现过，显然是不可能的。

后缀链接的定义 ​

上面提到，SAM 中每一个节点对应一个等价类，设 $s$ 为一个等价类中最长的字符串。

记串 $t$ 为最长的，不属于 $s$ 的等价类的，$s$ 的一个真后缀。$s$ 的等价类对应的节点的后缀链接连到 $t$ 对应的等价类。

即 $\text{link(s)}=t$。

由定义得，设一个等价类 $E$ 中最短的字符串是 $s_0$，则 $\text{link(E)}$ 中最长串的长度为 $\lvert s_0\rvert-1$。

这启示我们，如果知道 $\text{link}(E)$ 最长串的长度，就能得到 $E$ 中最短串的长度。所以 SAM 上只需要记录最短串长度即可。

由引理 2，$\text{endpos}(E)$ 包含于 $\text{endpos}(\text{link}(E))$。

所有后缀链接构成了一棵树的形态。对于每一个节点（等价类），其后缀链接节点中最长串长度，小于此节点最短串长度。则沿着后缀链接遍历，每一个等价类中的串长度只会减少，不会成环。此外，除初始节点 $P$ 以外，每一个点只有至多一条出边，且从任意节点一直跳后缀链接均可以跳到 $P$，故此图连通。则后缀链接形成了树的形态。

小结与记号约定 ​

• 原串 $S$ 每一个子串根据 $\text{endpos}$ 划分为多个等价类，每一个等价类对应 SAM 上的一个节点。

• 对于每一个节点（等价类）$v$，定义 $\text{long}(v)$ 表示其最长的串，$\text{len}(v)$ 表示其长度；$\text{short}(v)$ 为最短的串，其长度可以表示为 $\text{len}(\text{link}(v))+1$。

• 从任意点 $v_0$ 出发总能到达 $P$，经过的节点 $v_i$ 的等价类表示的串，均为 $\text{long}(v_0)$ 的后缀，且长度 $[1,\text{len}(v_0)]$ 恰好各出现一次。

• 所有后缀链接形成一棵以 $P$ 为根的根向树。

• 后缀链接也可以表示 $\text{endpos}$ 的包含关系：父亲节点包含儿子节点。

• 注意，后缀链接和 SAM 实际上是共用点，而各自有边的两张图。SAM 是一个 DAG，描述了字符串的转移，后缀链接树是树，描述了等价类的包含关系。

SAM 的线性构建算法 ​

先从算法流程出发，再分析原理。

算法流程 ​

此算法是一个 在线算法，每一次在已经构建好的串 $S$ 的末尾插入一个字符 $c$，对已有信息进行维护。

1. 记 $last$ 为上一次构建结束后停在的节点处，这个节点表示 $S$ 所属的等价类。在插入结束部分对 $last$ 进行更新。

2. 现在插入一个字符 $c$。新建一个节点 $cur$，将 $\text{len}(cur)$ 设置为 $\text{len}(last)+1$。

3. 从 $last$ 开始遍历 $last$ 的后缀链接，如果当前节点 $v$ 没有 $c$ 的转移，则加入一条 $v\rightarrow cur$ 的边，标记（边权）为 $c$。

4. 如果遍历到了起始节点 $P$，则到第 8 步。

5. 如果遍历到节点 $v$ 时，发现 $v$ 有到 $c$ 的转移，记当前节点为 $p$，其转移到 $q$。

6. 如果 $\text{len}(p)+1=\text{len}(q)$，将 $\text{link}(cur)$ 设置为 $q$，转到第 8 步。

7. 否则，创建一个 $copy$ 节点，复制 $q$ 的所有信息到 $copy$ 中，包括 $link$ 和所有出边。将 $\text{len}(copy)$ 设为 $\text{len(p)}+1$。

   然后，设 $\text{link}(q)=copy$，$\text{link}(cur)=copy$。

   从 $p$ 遍历后缀链接，设当前遍历到了点 $v$，若 $v$ 有边权为 $c$ 的出边，且连向 $q$，则将这条边连向 $copy$。

   如果 $v$ 没有边权为 $c$ 的出边，或是出边不连向 $q$，则停止遍历，转到第 8 步。

8. 把 $last$ 赋值为 $cur$，转到第 1 步。

算法原理 ​

1. $last$ 是 $S$ 串所属的等价类。

2. 现在插入字符 $c$ 之后，必然产生一些新的子串，这些子串是 $S+c$ 的一个后缀，其 $\text{endpos}$ 集合必然包含新的末尾位置。所以一定会产生新的等价类，新建一个 $cur$ 节点记录该等价类的信息。此等价类的最长串显然是 $S+c$，其长度为 $\text{len}(last)+1$。

3. 从 $last$ 遍历后缀链接，遍历到的节点均为 $S$ 的后缀，且一直没有遇到有 $c$ 转移的。考虑某一个后缀 $s$ 没有到 $c$ 的转移，那么 $s+c$ 必然属于 $S+c$ 这个等价类集合。

4. 如果走到了初始节点 $P$ 也没有遇到转移 $c$，说明 $c$ 在原串中没有出现过，此时直接结束即可。

5. 如果遇到一个节点有到 $c$ 的转移，就需要进行一些维护。

6. 由于 $\text{endpos}(p)$ 的真包含 $\text{endpos}(last)$，必定存在一些位置在 $\text{endpos}(p)$ 而不在 $\text{endpos}(last)$ 中。且 $\text{long}(p)$ 是满足这个条件的最长的串。

   由于 $p$ 有边权为 $c$ 的转移，故 $\text{long}(p)+c$ 是原本存在的，且这个串是满足，最长的，与 $S+c$ 的 $\text{endpos}$ 集合不同的串。

   如果 $\text{len}(p)+1=\text{len}(q)$，则 $\text{long}(p)+c$ 是 $q$ 等价类中最长串，直接将 $cur$ 的后缀链接连到 $q$ 即可。

7. 如果不满足上述条件，说明 $\text{long}(p)+c$ 不是 $\text{len}(q)$ 中最长的串，那么需要将 $q$ 分裂为两个部分。

   一部分的长度在 $(\text{len}(p)+1,\text{len}(q)]$ 之间，这部分并不会作为 $S+c$ 的后缀出现，故其 $\text{endpos}$ 集合与新的等价类不同。所以建立一个 $copy$ 节点，将 $q$ 节点的信息复制到 $copy$ 节点上（包括转移等），再将 $copy$ 节点的 $\text{len}$ 设为 $\text{len}(p)+1$。前一部分仍然使用 $q$ 这个节点。

   修改后缀链接：

   • $copy$ 继承的是 $q$ 中较短的一些后缀，其后缀链接应当为原来的 $\text{link}(q)$。事实上这一步在复制 $q$ 到 $copy$ 的时候顺便进行了。

   • 上一段提到，前一部分的 $\text{endpos}$ 集合应当是这一部分的真子集，根据定义，将 $\text{link}(q)$ 修改为 $copy$，$\text{link}(cur)$ 也修改为 $copy$。

   还有一些东西需要修改：原本一些节点通过边权为 $c$ 的边转移到 $q$，现在，有一些应当转移到 $copy$，另一些转移到新的 $q$。沿着 $p$ 继续遍历后缀链接，假设到了点 $v$。

   • 若 $v$ 有一条边权 $c$ 到达 $q$ 的边，由于 $v$ 是 $p$ 的后缀（后缀链接定义），则 $v+c$ 一定在 $copy$ 集合内，将这条边重定向到 $copy$。

   • 若 $v$ 有边权为 $c$ 但是不连向 $q$，其一定连向 $q$ 在后缀链接树上的一个祖先，此时不能将其重定向。此时 $v$ 的祖先连向的必然也是 $q$ 的祖先，所以也不能重定向，此时无需继续遍历。

   • $v$ 可能出现没有边权为 $c$ 的边的情况吗？

SAM 的复杂度 ​

假设字符集大小为 $\lvert \Sigma\rvert$，字符串长度为 $O(n)$，则：

• 若每一个节点使用 $O(\lvert \Sigma\rvert)$ 的空间，记录每一个边权的转移，还需要一些辅助的东西，做到 $O(n\lvert \Sigma\rvert)$ 的空间复杂度，$O(n)$ 的时间复杂度。

• 如使用 map 进行实现，则可以做到 $O(n)$ 的空间复杂度和 $O(n\log \lvert \Sigma\rvert)$ 的时间复杂度。

当字符集较小（例如 26）时常用第一种做法。

SAM 的应用 ​

统计子串 ​

子串是前缀的后缀，在 SAM 的构造中，我们逐个向 SAM 中插入字符，则每一次新建的 $cur$ 节点表示前缀所属的等价类。$cur$ 节点在 $\text{link}$ 树上的祖先则是 $cur$ 的后缀，也就是前缀的后缀。于是，只要知道哪些节点是前缀所属的等价类，找这些点的祖先就能统计到所有子串了。

Problem A 【模板】后缀自动机 ​

Link

求一个字符串 $S$ 每一个出现次数不为 $1$ 的子串长度乘以出现次数最大值。

$1\le \lvert S\rvert \le 2\times 10^{6}$

Problem B 【SDOI 2016】 生成魔咒 ​

Link

初始有一个空串 $S$，每次操作加入一个字符 $x$，求每次操作后本质不同的子串数量。

$1\le x\le 10^{9},1\le n\le 10^{5}$。

Problem C LCS ​

Link 或 Link

求两个字符串的 LCS 的长度。LCS 指最长公共子串。

$1\le \lvert s_1\rvert,\lvert s_2\rvert\le 2.5\times 10^{5}$

另外 这道题 也挺类似的，但是有点不同，可以做一做。