凛冽的风……

仿佛要将这最后的，仅剩的，微不足道的，存在的意义，剥下呢……

大概今年 6 月的时候用后缀树推了一遍 Blumer 的后缀自动机构造算法，还考虑了一些其他相关的东西，不过并没想清楚……前不久听说北大集训出了这样的题，于是就把这个坑填上了……这次要写的是，写起来要考虑的东西略多的维护双向加字符的字符串的隐式后缀树，就当是给大家的圣诞节礼物吧。

6 月时写过用后缀树解释 Blumer 的后缀自动机构造算法，但可能不是很能看，所以就没有发出来了。

阅读这篇文章需要前置技能 Ukkonen's algorithm 并会用后缀树解释 Blumer 的后缀自动机构造算法，以下仅作简要的介绍。

Ukkonen's algorithm 维护了字符串的隐式后缀树，并支持向后增加字符。

隐式后缀树是将后缀 trie 中所有只有一个孩子的结点和它的孩子合并后得到的树，这相当于字符串中所有只出现了一次的后缀的 trie 按后缀树的合并方法合并后得到的树。可以注意到未加入的后缀是所有后缀中最短的一些。

算法维护了最长的未加入的后缀在树中的位置，向后增加字符时，已加入的后缀会增加一个字符，维护的位置也会发生改变，如果树中没有新的位置，那么加入一个后缀，继续检查更短的后缀的位置。

快速找到更短的后缀的位置需要使用后缀链接，一个结点的后缀链接是将当前结点对应的最长的字符串的第一个字符去掉，得到的字符串对应的结点，这个字符串也是这个结点对应的最长的字符串。

Blumer 的后缀自动机构造算法维护了字符串的后缀树，并支持向前增加字符。

向前增加字符相当于加入一个后缀，于是需要找到这个后缀的在树中的最长的前缀在树中的位置，在这个位置加入一个结点。

加入结点的位置可以用后缀自动机的转移快速找到，后缀自动机的转移和后缀链接相反，是在当前结点对应的字符串前增加一个字符，得到的字符串对应的结点，根据 begin-pos 等价关系，容易发现所有串对应的结点是相同的。

显然，如果需要向后增加字符，只能维护隐式后缀树，否则非叶后缀结点的变化将难以维护。于是考虑在 Ukkonen's algorithm 基础上维护类似后缀自动机转移的东西，并用类似 Blumer 的算法的做法支持向前增加字符。

首先需要对隐式后缀树定义转移。

非叶结点到非叶结点的转移和后缀树没有什么区别，用后缀树的性质容易看出是良好定义的。

对于非叶结点到叶结点，我们认为有转移当且仅当非叶结点对应的所有字符串前增加一个字符，得到的字符串都对应这个叶结点。

对于叶结点，显然只有某个后缀对应的结点到长度比它大一的后缀对应的结点的转移。

现在考虑 Ukkonen's algorithm 过程中需要怎么维护转移边。

加入后缀时，如果有加入非叶结点，需要复制它的孩子的所有转移。

如果是这次增加字符导致的第一次加入后缀，那么加入位置结点增加一个到上一个加入的后缀结点的转移，否则增加一个到上一个加入位置结点的转移。

加入的后缀结点有一个到上一个加入的后缀结点的转移。

如果加入了一个非叶结点，显然需要将一些转移修改为到它，这在找下一个后缀的位置时顺便修改即可。注意加入位置结点为根和加入位置结点的 parent 为根的情况。

最后需要检查最长待加入后缀是否和维护的位置的结点对应的最长串相同，如果是，维护的位置的结点增加一个到上一个加入的后缀结点的转移。

现在考虑怎么向前增加字符。

主要框架和 Blumer 的算法类似，但注意到加入一个后缀可能会使一个后缀结点变为非叶结点，这可以通过检查 Ukkonen's algorithm 维护的位置判断。

分裂结点时可能会影响 Ukkonen's algorithm 维护的位置相关的信息，分裂出的结点可能会增加一个到最短已加入后缀的后缀结点的转移。

时间复杂度分析与 Ukkonen's algorithm 和 Blumer 的后缀自动机构造算法基本相同，可能某些分析方法的势函数需要改变。

这个方法有和 Ukkonen's algorithm 和 Blumer 的后缀自动机构造算法相同的时间复杂度，但写起来要考虑的东西略多，不知是否能找到更简单的实现或更好的做法。

更进一步的扩展不在本文讨论范围内，相关内容参见 维护双向加字符的字符串。

北大集训2018 Day3 close AC 代码，可能实现得并不优美（