后缀自动机（SAM）
给一个可以画出 SAM 结构的网站。（从机房大佬那里偷的）但听管理大大说这个东西画广义 SAM 的时候有点问题，详细见洛谷讨论 悲惨故事 长文警告 关于广义 SAM 的讨论。
然后洛谷管理大大给了一个他自己做的网站：SAM Visualizer。就是好像会在随机时间 404 掉。
模板
简介
SAM 几乎可以算是信息竞赛中字符串的终极解决方案。几乎所有的比较难的字符串题都可以通过 SAM 的性质结构之类的东西延伸出来。
事实上，更准确的说 SAM 更像数据结构，是一种与 tire 树类似的东西。
其结构是一张 DAG 与 一棵树的和，这二者的点集都是一样的。DAG 上的边与 trie 上的类似，都是表示一个字母。
通过走 DAG 上的边，我们可以表示这个字符串的所有子串，通过走 parent 树上的边，我们可以表示所有当前节点表示的子串的所有后缀。
endpos
endpos 实际上是一个集合。具体而言，endpos 是 \(s\) 的字串 \(s'\) 在 \(s\) 中出现位置的末尾的集合。
因此，根据定义，显然有性质：（下面简写 endpos 为edp，\(edp(a)\) 表示字串 \(a\) 的 edp 集合，所有 edp 集合相同的字串所构成的集合成为 edp 等价类）
[*]\(edp(a)\subseteqedp(b)\Leftrightarrow b\) 是 \(a\) 的后缀
[*]\(edp(a)\nsubseteq edp(b)\Leftrightarrow b\) 不是 \(a\) 的后缀
[*]同一 edp 等价类中所有字符串长度不等且连续
我们发现一个 edp 等价类里的所有字串具有类似的性质，因此我们考虑将所有 edp 等价类的字串变成一个点来看待。
根据简介里的介绍，我们发现如果我们创建出一张 DAG，可以像 trie 一样通过走 DAG 上的边到达所有后缀，那么就可以表示所有子串了。（任意一个子串都一定是某个后缀的前缀）
这个就是其叫“后缀自动机”的理由，我们从根节点走到叶子结点一定表示了一个原串的后缀，而我们将所有某个 edp 等价类中的点压缩到了一个节点上，这样就形成了一个 DAG。
这里以 abbb 为例。请先忽略掉红色的边。
后缀链接 \(link\) 及parent树
由于一个 edp 等价类中所有的字符串长度相同且连续，因此如果我们将某个 edp 等价类中的最短的那个字符串的最前面的字符删去，那么新得到的这个更短的字符串就一定在更多的地方出现过。
我们将更短的这个字符串所在的 edp 等价类所对应的点与原来的 edp 等价类所对应的点连边。这就是所谓的后缀链接。
根据定义，我么可以发现空字符串所对应的节点不会有边连出，而其他每个节点有且仅有一条边连出。因此所有的后缀链接以及点构成了一棵树。我们将这棵树称作 parent 树。对于一个点 \(u\)，我们将其连出的后缀链接所指向的点称作 \(fa_u\)。
反过来看，如果我们将连边的过程看成在当前节点对应的最长的字符串前面加点，然后向加点的字符串的对应的点连边，那么显然可以看出其子节点的 edp 集合是当前点的 edp 集合的一个划分，其所有子集和的 edp 集合不交且包含于当前节点的 edp 集合。
不过需要注意的是，其所有子节点的 edp 集合的并可能并不是其的 edp 集合。
我们设 \(len_u\) 表示节点 \(u\) 所代表的所有字符串中最长的长度，\(minlen_u\) 表示最短的长度。根据定义显然有 \(minlen_u-1=len_{fa_u}\)。这个结论比较重要。
仍然是那个例子，按照上面的定义将后缀链接建出来就是上面那张图中红色的边。点上的 \(Max\) 表示的就是这个点所对应的 \(len\)。
线性构造
然后就来考虑如何建出这两个东西。我们通过一个一个将字符插入进 SAM 来构造。假设我们当前插入的是字符 \(s_i\)，而 \(\) 所代表的字符串的 SAM 已经构建完毕。
在具体讲述之前，先需要强调的是我们不具体保存下来每一个点所对应的 edp 集合是什么以及所对应的字符串是什么。我们只是存下来了后缀链接、DAG 上的边和 \(len\)。（\(minlen\) 不需要记是因为可以通过 \(fa\) \(O(1)\) 求）
我们设 \(lst\) 表示前 \(i-1\) 个字符所对应的字符串所在的节点编号。
显然对于一个新的字符及其位置，我们需要一个新的点来表示，设为 \(u\)。而且其 \(len\) 一定 \(len_{lst}+1\)。
我们假设一个变量 \(p\)，其初始值是 \(lst\)。可以发现如果 \(p\) 所对应的点在 DAG 上没有 \(s_i\) 的出边，那么在这个点所对应的所有字符串后面都加上一个 \(s_i\)，那么这所有新的字串的 edp 一定都包含 \(i\) 这个位置。因此我们将 \(p\) 新增一条在 DAG 上的指向 \(u\) 的边。注意这时 \(p\) 是 \(lst\)，\(lst\) 的 edp 集合中一定有 \(i-1\) 这个位置。
然后发现如果令 \(p\gets fa_p\) 并且跳了 parent 树上的边后新的 \(p\) 在 DAG 上 仍然没有 \(s_i\) 这条边，上述逻辑依然成立。注意，在 parent 树上跳 \(fa\) 本质上是在前面删去节点，跳后节点中的所有子串一定是跳前节点中子串的真后缀。这样 \(p\) 中的所有子串的 edp 集合中仍然一定有 \(i-1\) 这个位置。
如果 \(p\) 一直到达最初表示空串的节点，那么表示这个字符是新出现的，将 \(fa_u\) 设为表示空串的节点即可。
如果某个时刻 \(p\) 在 DAG 上有这条边，那么设 \(q\) 为 \(p\) 走 DAG 上 \(s_i\) 的边所到达的点。
由于 \(p\) 所代表的所有字符串仍然是前 \(i-1\) 个字符所表示的字符串的后缀，因此在后面加上一个节点 \(s_i\) 后字符串也理应是前 \(i\) 个字符所表示的字符的后缀。
但是有可能会有从其他方向连来的边 DAG 上的边到 \(q\)，因此可能会分为两类串：
[*]长度小于等于 \(len_p+1\) 的字符串，其来源一定是 \(p\) 中的字符串后面接上一个 \(s_i\) 来的。
[*]长度大于 \(len_p+1\) 的字符串，其来源一定不是 \(p\) 后接上 \(s_i\)，也就是说这些串一定不是前 \(i\) 个字符所组成的串的后缀。
发现加上 \(s_i\) 之后第一类点的 edp 集合会多上 \(i\) 这个位置，而第二类点的 edp 集合保持不变，同时我们的 \(fa_u\) 一定是连向第一种情况中的字符串。因此我们需要将 \(q\) 拆成两个点来看待。特别的，如果 \(len_q\) 已经等于 \(len_p+1\)，那么无需拆点，直接 \(fa_u\gets q\) 即可。
考虑如何拆点。我们新建点 \(nq\) 表示第一类字符串所表示的点，原来的 \(q\) 表示第二类字符串所表示的点。
我们先让 \(nq\) 继承 \(q\) 的所有信息，然后根据上面有 \(len_q\gets len_p+1\)。由于原来的 \(q\) 中的所有子串共后缀且长度连续，因此第一类点的所有字符串都是第二类点的字符串的后缀，且一定是最长的能找到的后缀。因此有 \(fa_q\gets nq\)。
然后所有 \(p\) 的后缀然后走 DAG 上 \(s_i\) 这条边如果原来走到的是 \(q\)，那么现在走到的一定是 \(nq\)。如果不是 \(p\) 的后缀的，那走到的一定仍然是 \(q\)。
因此我们通过一直跳 \(fa_p\) 的方式来修改对 DAG 的影响。
然后有一些细节可能要仔细想想。比如说 edp 集合实际上是一直在变的。由于我们没有记录每个节点具体的 edp 集合长什么样，因此除了 \(q\) 节点，其他所有节点的对应的字符串的 edp 集合都是同步变动的，我们并不需要去管。
SAM诸如此类的细节问题实际上不少，但是这里就不一一赘述了。
然后就做完了。下面是插入第 \(x\) 个字符的代码。变量名基本和上面的一致。
void insert(int x){
int u=++idcnt,p=lst,v=s-'a';a.len=a.len+1;
while(p&&a.ch==0) a.ch=u,p=a.fa;
if(!p) {a.fa=1;}
else
{
int q=a.ch;
if(a.len==a.len+1){a.fa=q;}
else{
int nq=++idcnt;a=a;
a.len=a.len+1,a.fa=a.fa=nq;
while(p&&a.ch==q) a.ch=nq,p=a.fa;
}
}
lst=u;
}复杂度
复杂度的话空间显然是线性的。
时间的话应要求简要叙述一下。
我们发现我么只需要证明 SAM 所包含的点数与边数都为线性即可证明 SAM 的时间复杂度为线性。
首先点数是线性的这个相对显然，因为每一次插入最多分裂出一个点来。
对于边，我们将其分开来考虑。
后缀链接显然是线性的，毕竟构成一棵树同时点数是线性的。
DAG 上可能加边的地方有两个：开始时向上跳后缀链接连边以及分裂点后向上跳后缀链接修改 DAG 上的边。
对于第一种情况，由于点数是线性的，字符集大小是常数，因此复杂度是线性的。（好像可能可以类比一下 AC 自动机？实际上均摊下来每个点都只会被修改一次，。但不管怎么说都一定是线性的。）
对于第二种情况，就比较复杂了，让我们借鉴一下 oi wiki 的思路。
我们设 \(t\) 表示 \(p\) 这个节点表示的最长的字符串，显然这是 \(\) 这个字符串的一个后缀。每迭代一次，\(t\) 的长度一定递减。
可以发现，在这个循环开始前，最初的 \(p\) 距离 当前的 \(lst\) 至少要经过 \(2\) 条后缀链接。
这最后一句话很难理解：在这个循环结束后，最后的 \(p'\) 对应 \(t'\)，有字符串 \(t'+s_i\) 成为路径上第二个从 \(u\) 出发的后缀链接。而在下一轮中，当前的 \(u\) 又会成为新的 \(lst\)。（好像也找不到更好的表述方式）
因此，作为当前字符串的后缀的字符串：\(link_{link_lst}\) 这个点最长的字符串，其在字符串中的位置一定单增。这样就有这个位置至多单增 \(n\) 次，也就证明了第二部分的复杂度是线性的。
最后观察到 SAM 的时空复杂度都要带一个字符集大小的系数。如果字符集过大，可以用 map 来保存 DAG 上的边，但是复杂度会多一个 \(\log\)。
线段树合并维护 edp 集合
有的时候我们的确需要使用 edp 集合来判断或维护一些东西了，怎么办呢？
我们考虑一个 edp 最初的出现可能在哪里。可以发现一定是在每次插入的新节点一定是这个 edp 第一次出现的地方。
又由于在 parent 树上的一个节点的 edp 集合是其儿子的 edp 集合的并集，因此考虑按拓扑序从下向上一次维护。
考虑用线段树直接从下向上合并。这里有两种写法。一种是可持久化线段树合并，另一种是普通线段树合并。二者在实现上的本质区别只有在合并的时候是否新建一个节点。可持久化线段树在复杂度上的唯一区别是空间复杂度是普通版的 \(2\) 倍。二者的时间复杂度都是 \(O(n\log n)\)，常数也差不多。
二者在应用上的区别是是否可以一边合并一边统计答案。如果有多测那肯定需要可持久化了。
下面是可持久化线段树合并的示例。
namespace sgt{ int ls[N
页:
[1]