广义后缀自动机概述

广义后缀自动机的前置知识点是后缀自动机和字典树（Trie树）的相关内容，因为这两个知识点穿插在一起更容易理解和构建知识框架。

当我们的是动机如何储存一个字符串的所有子串？该怎么办？怎么做？后缀自动机的作用就展现出来了。

首先，后缀自动机起源于刘研绎在其 2015 国家队论文《后缀自动机在字典树上的拓展》上提出的一种结构，即将后缀自动机直接建立在字典树上。

广义SAM是一种用于维护Trie的子串信息的SAM的简单变体。将多个模式串插入到Trie后，即可使用广义SAM维护多模式串的信息。这是广义SAM最广泛的应用之一，其基本思想是将多串的信息进行压缩，使得SAM在仍满足节点数最少的同时 包含所有子串的信息。此时SAM中的一个状态可能同时代表多个串中相应的子串。

一种显然的做法是先使用多个模式串构造Trie树，再在Trie上构建SAM。

常见的伪广义后缀自动机：

（1）通过用特殊符号将多个串直接连接后，再建立 SAM；

（2）对每个串，重复在同一个 SAM 上进行建立，每次建立前，将last指针置零。

方法1和方法2的实现方式简单，而且在面对题目时通常可以达到和广义后缀自动机一样的正确性。所以在网络上很多人会选择此类写法，例如在后缀自动机一文中最后一个应用，便使用了方法1 。

但是无论方法1还是方法2，其时间复杂度较为危险。

字典树的使用也是尤为需要注意的一点，首先应对多个串创建一棵字典树，这不是什么难事，如果你已经掌握了前置知识的前提下，可以很快的建立完毕。这里为了统一上下文的代码，给出一个可能的字典树代码。

后缀自动机的建立：如果我们把这样一棵树直接认为是一个后缀自动机，则我们可以得到如下结论：

对于节点i，其 len[i] 和它在字典树中的深度相同

如果我们对字典树进行拓扑排序，我们可以得到一串根据 len 不递减的序列。BFS的结果相同。