SAM

有点忘了。省选前来复习下。

一个节点有几个信息：父亲。表示 \(endpos\) 集合最小的，且是当前节点 \(endpos\) 集合超集的节点。转移状态（儿子），表示加入某个字符能转移到的位置。\(len\)，表示节点表示的这些子串的最长长度。

考虑构建。首先有一个根（表示空集）。

每次插入一个字符 \(c\)，新建一个节点 \(np\) 来表示目前整个串的状态。\(np\) 的长度显然是目前。

然后从插入前表示整个串的节点 \(last\) 开始往上跳，将跳到的所有点的 \(c\) 这个儿子全部设成 \(np\)，直到跳到根或者有一个节点有 \(c\) 这个儿子为止。

如果跳到了根，把 \(np\) 的父亲设为根即可。

如果跳到一个非根节点，继续分类讨论。

设这个点是 \(p\)，其通过 \(c\) 这个儿子转移到的点是 \(q\)。

如果这个 \(len_p+1=len_q\)，那么直接将 \(np\) 的父亲设为 \(q\)。

否则新建节点 \(nq\)，初始所有状态全部和 \(q\) 相同，然后将其长度设为 \(len_p+1\)，并将 \(q\) 和 \(np\) 的父亲设为他即可。同时注意跳父亲把所有 \(c\) 儿子是 \(q\) 的替换成 \(nq\)。

后缀自动机可以亿些事情。

首先求 \(endpos\) 集合大小：直接将每次新建的 \(np\) 的 \(endpos\) 集合大小设成 \(1\)，然后一个节点的 \(endpos\) 集合大小按节点父亲建立的 parent tree 上的子树的这些 \(1\) 之和。

然后性质是，一个节点的所有儿子的 \(endpos\) 集合不交，且其并集是该节点的 \(endpos\) 的子集（不一定是真子集）。

求两个串的最长公共子串直接建出一个串的后缀自动机然后用另一个串从前往后枚举，存在这个儿子就跳过去，并将计数器加一，不存在就跳父亲，并将计数器设为父亲的 \(len\) 即可。

计算本质不同子串数或字典序第 \(k\) 大子串都是简单的。因为 SAM 上任一条路径跑出来得到的字符串都是唯一的。

首先按照拓扑序逆着算，每次更新一个节点后面的状态数，然后算本质不同数是简单的，算字典序第 \(k\) 大就直接从小到大枚举字符看能否走过去即可。非严格第 \(k\) 大需要将计算过程中的 1 改成 \(endpos\) 集合大小。