SAM
sam，后缀自动机复习。
待更新。
会过sam,但是忘了，网上教程像是一步一步喂你饭真心很烦。。。
还是得自己写一写，上次自学的时候总结了一些，但那时候还觉得别的写的可能好一点，真是巨大错误。。。
\(endpos\rightarrow right\) 集合。
\(fail\rightarrow parent\) 树。
\(right\) 集合中最大的长度 \(l\)。
注意sam的构造方式是增量构造，你需要管插入的串的正确性，其余的自然正确。
插入一个字符，我们需要把以这个字符为结尾的所有串插入parent树。
为了描述简单易懂现在往 i 位，插入 c，字符串记为 s。
首先，从上一个最后的后缀往上跳，看dag什么时候有 c 的出边。
注意parent 树跳父亲本质在缩短后缀。
如果没有，那么新建节点 w，parent树父亲是根，相当于把 s[k:i] \(k\leq n\) 全部插入，用 w代替了。
然后把刚才跳过的父亲的 c 出边全连到 w。
考虑刚才跳父亲本质上在跳插入前串的后缀。
否则设当前 dag 有 c 出边的点为 d，\(trans(d,c)=x\)。
那么尽管 d 是原串一个后缀，x 也有可能不是仅仅是新加入后缀，而有可能比新加入的要长。
eg: c='b',d="aaa",x="ccaaab"。
这个 x是要比我们插入 c 后的后缀 "aaab" 长，也就是说我们新加入的 \(right\) 集合更大应该做父亲。
所以我们就判断一下 \(l(d)\) 与 \(l(x)\) 的关系。
如果 \(l(d)=l(x)+1\) 那么就是插入后后缀和 x 长度一样，不用当爹，直接新建节点 w，按照 1那样把符合的新状态在 dag 上连边。w 在 parent 树上直接认 x 为爹。
本质上在把一部分后缀直接插入，作为 w，剩下的都是原自动机可以表示的。
否则 \(l(d)<l(x)+1\) 我们必须把这个 x 所在的 \(right\) 拆开。
我们就把集合 \(right_x\) 拆成 \(A=\{d+c\}\) 和 \(B=\{k\in right_x\mid length(d+c)<length(k)\}\)，注意 \(length\) 含义是字符串长度 。
同理新建 w，dag 连新边，w 认 \(A\) 为爹，\(B\) 认 \(A\) 为爹。
注意 A,B dag 连边情况和 x 一样，还有记得把以前dag向 x 连边的改成向 A 连边。
本质上在把一部分后缀直接插入，作为 w；特殊独立出来 d+c 这个后缀；然后别的也是原先自动机可以表示，只不过多了点改边操作。
注意我们一个个插入后缀本质上是把所有字串都插入了。
注意：每一个parent树上结点，可以对应一个dag上结点，为什么，考虑我们往字符串后加字符，这些后缀不会发生改变。
构造SA。
主要通过做法理解正确性。
反串的parent树就是后缀树。
构造SA呢，就是建出反串后缀树，然后考虑一个 rightpos 中最长的串，他的儿子都是相当于在原串中加后缀。
而且
这些串加的第一个字符必定互不相同。我们只需要维护这个串第一次是在哪个后缀被加入的，就能简单地维护出该位字符时什么。
所以他们的字典序可以很好排出。
仔细想一下反串后缀自动机每一次都是加后缀反串。然后考虑parent树每一次跳前缀，进而sort