今天看了一个多串pam题，然后就来看看。
简单dfa
最简单的dfa，比如，前缀自动机。前缀自动机的合并就是trie合并。
如果你需要支持给一个trie挂叶子，更新合并后的trie，你发现这个好像很简单，只要在合并掉一个点的时候记录它指向了谁，然后并查集维护一下即可。
pam
妈的，空的之言可谓切中了肯綮。pam就是个带suffix link的trie，让你可以插入一个字符。当你要合并pam的时候，简单地合并一些trie。
也可以直接在一个pam上进行插入一个新串，因为插入一个串的时候suffix link已经确定了，所以suffix link是不受插入影响的。甚至可以动态给任何串加字符。只需要特判一下我们将要插入的点是不是已经存在了。
一般dfa
于是我们考虑能不能从合并的角度考虑这个问题，发现如果我们想要合并任意两个dfa，可以先建立一个不一定最小的它们的并，然后进行最小化，而并可以考虑，新dfa的状态是原dfa的笛卡尔积。
比如有个题是xix open cup gp of gomel J. Ten Ranges，大概需要你给若干个 不包含某个串作为子序列的dfa 求交。直接全笛卡尔积起来状态数爆炸，可以猜测可达的状态数其实很小然后搜出可达状态跑dfa最小化，但是并没有这个必要，合并到最后状态数我记得只有$19$，那么用这个每次合并两个的方法看起来就可以保持状态数很少了。
不是很清楚subsequence am笛卡尔积的状态数估计，看起来跟字符集有很大的关系。另外存在方法在相差串数的指数级(如果有$k$个串，相差$k!$倍，实际上完全不满)的情况下，线性时间内构造近似的多串subsequence am。
基于fail的dfa
这是比较主要的部分。
我们平时用到的单串dfa有kmp pam sam，它们都是基于suffix link的。刚才已经说过pam是一个trie，kmp是一条链，但是有环，而sam是最小化的trie。
kmp
离线构造acam的话，考虑先把trie建出来，然后和kmp几乎一样求suffix link。
如果想要在线构建acam，比较困难，因为像sam，一个串在后缀trie中出现时，它的suffix link就确定了，但是acam的suffix link变化量可能很大。为了卡这个，考虑有一个$abbbb…$，然后我插入$bbbbb…$，suffix link变化$\Theta(n^2)$次。
如果每次插一整个串，那么容易证明变化次数(也就是插入同一个串过程中，变多少都算一次)是$O(n\sqrt{n})$的，因为每次suffix link变化必然是变长，而你用长$\leq \sqrt{n}$的串不可能让suffix link的深度变得超过$\sqrt{n}$，$>\sqrt{n}$的只有$<\sqrt{n}$个。构造卡满也是简单的。但是这东西没啥用，因为很难找到哪些位置变化了。
sam(blumer)
重头戏。sam是所有子串的trie最小化得到的，那么多串sam，也就是trie合并之后最小化。经典的，最小化是压缩后续转移完全相同的点为一个，所以这里的最小化对应于压缩suffix link树上的单链(如果一个点只有一个儿子，那么把它和它的儿子合并)，这样的点在suffix link树上的子树是相同的。先描述一下sam如何插入，然后尝试照葫芦画瓢 :
考虑插入一个字符$c$之后，后缀trie会产生一些新的点，也就是在原来的每个后缀后面挂一个叶子，显然它们被suffix link连成一串，其中最长的若干个是第一次出现，剩下的都已经出现在前面的点中，不需要再建出来。这些第一次出现的当然不会被别的串连到，于是我们必然在后缀trie的suffix link树上挂了一条单链，那么这个单链会被合并成一个叶子。有可能这个叶子接在一条被合并起来的边的中间，而不是一个点上，此时需要从这条边中间分裂出一个点来。
具体的，为了确定这些点都在哪，经典的有$\mathrm{fa}(\mathrm{link}(u))=\mathrm{link}(\mathrm{fa}(u))$，因为suffix link就是删掉第一个字符，fa就是删掉最后一个。我们不停向上跳suffix link，直到发现当前这个长度的串已经出现过了，也就是跳到一个点$p$满足$v=\mathrm{ch}(p,c)$存在，那么此前所到的点的$\mathrm{ch}(…,c)$应该连向新叶子，而继续往上的点应该连向$v$或者suffix link树上$v$的祖先，$v$的祖先这部分看起来不会变化。这里需要特判所有$p$都没有$\mathrm{ch}(p,c)$。注意有可能$\mathrm{ch}(p,c)$本来应该是$v$在suffix link树上的父边上被压起来的一个点，此时我们就需要把它拆出来，可以使用$\mathrm{maxlen}$判断这一点。
那么考虑多串sam。注意到suffix link也是不受插入影响的，那么我们看起来就可以放心大胆的直接插入了。这里可能我们要挂的新叶子也出现过(也不一定是叶子)，此时需要直接返回它。注意它可能是一个点，也可能被压缩在一条边里面，如果被压缩在一条边里面，需要先把它分裂出来。
所以是不是sam也可以给任意串加字符。
st(ukkonen)
感觉上也只需要在一开始加一个类似的特判。