广义后缀自动机是后缀自动机（SAM）的多串扩展。它可以识别一棵 Trie 树上从根到任意一点的路径。

广义 SAM 的每个状态同样由转移边 trans[]，parent 链 par 以及该状态所表示的最长子串 len 三部分组成。它们的意义与 SAM 相同。下面内容设字符集为 A。

性质

状态数

一棵给定 Trie 树 T 的广义 SAM 的状态数为线性，即 O(|T|)。

证明：

与普通 SAM 的证法类似。容易证明两个状态的 right 集合要么是包含关系要么交集为空。因此广义 SAM 的 fail 链也会构成一棵树，而每个状态 parent 树上的父亲的 right 集合真包含该状态的 right 集合。对于有多个儿子的状态，可以将其映射到一个自己包含但儿子不包含的位置。这样原树可以转化为一棵每个点的儿子数不为 1 且叶子数不超过 |T| 的树，这样的树的节点数是不超过 2|T|-1 的（考虑完全二叉树）。因此原命题得证。

转移数

众所周知，普通后缀自动机转移数是线性的，但广义 SAM 不具有这样的性质。

一棵给定 Trie 树 T 的广义 SAM 的转移数为 O(|T|\cdot |A|)。

证明：

已知广义 SAM 的状态数是线性的，而每个状态最多有 |A| 个转移边，因此总转移数为 O(|T|\cdot |A|)。命题得证。

为什么会和单串 SAM 不同呢？回想一下字符串 s 的后缀自动机的转移数证明：

从空状态开始，在转移 DAG 上找到一棵有向生成树，树边数显然是 |s|-1。再考虑每条非树边 (p,q)，其对应字符为 c。设从空状态出发，走树边到达状态 p 的路径为 u；从 q 出发，走树边到达终结状态的路径为 v。那么 u+c+w 将是 s 的一个后缀，且对于每条树边都不同（唯一经过了 (p,q) 这条边）。将这条树边映射到这个后缀上，可得知非树边数不超过 s 的不同非空后缀数，即 O(|s|)。总转移数即为树边与非树边数之和，也为 O(n)。因此原命题得证。

然而 Trie 树可能有 |T|\cdot |A| 个不同非空后缀，因此非树边数也是这个级别的。下图就是一个可以达到这个上界的例子：

这棵 Trie 的形态是一棵椰子树，其中链的长度为 O(|T|)，链末菊花的大小为 O(|A|)。链上为相同的字符，菊花上的字符两两不同。很明显它有 O(|T|\cdot|A|) 个不同非空后缀。对于每个由若干链上字符组成的子串，它的 right 集合显然是不同，因此在广义 SAM 中对应的状态也不同。每个这样的状态都可以走任意一个菊花上的字符转移到一个终结状态，所以这个 SAM 转移数是 O(|T|\cdot|A|) 的，也就是我们的上界。

所以，在字符集过大时，最好不要使用广义后缀自动机。

构造

广义后缀自动机的构造方式比较多，下面介绍几种常见的构造。

离线构造

这种方法一般用于给定了 Trie 树 T 的情况，当然也可以直接用给出的串建出 Trie。

根据上文的性质，任何构造算法的复杂度都有一个下界为 O(|T|\cdot|A|)。而这种算法就达到了这个下界，且实现也比较容易理解。

在 Trie 树上 BFS，插入一个字符时，只需将广义 SAM 的 last 指针设为它的父亲，然后按普通后缀自动机的方式插入即可。

这样做的正确性是显然的，因为 Trie 树中之前从未出现过当前前缀。