对称压缩后缀自动机

后缀树，把所有后缀插到一个 $\rm Trie$ 里，然后对其进行压缩，每个节点都表示了一个 $\rm left$ 集合。

根据 $\rm DFA$ 最小化理论，接下来可匹配的后继相同，那么它们就会被压缩到同一个节点，所以每个节点都表示了一个 $\rm right$ 集合（ $\rm endpos$ ）。

显然，后缀自动机和反串后缀树的点集是可以形成对应关系的。

若一个点的自动机后继的 $\rm right$ 集合大小与它相同，显然这样的后继只有一个，我们把两个点压缩在一起，形成的结构我们称作“压缩后缀自动机”。

考虑这样做的意义，相当于我们对每个点找到了它的“上下文”（ $\rm context$ ），也就是说在保证 $\rm right$ 集合大小不变的前提下，先尽力向左扩展再尽力向右扩展得到的串。

扩展的顺序是无所谓的，因为这相当于对 $\rm right$ 集合先求 $\rm lcp$ 再求 $\rm lcs$ ，两部分显然是独立的。

压缩后的后缀自动机其实并不符合自动机的定义，一条边并不是一个字符，但是我们 $\rm context$ 的定义十分友好，不难看出正串和反串的等价类划分是完全一致的，也就是说，我们可以将正串和反串的压缩后缀自动机叠起来，形成的结构我们称作“对称压缩后缀自动机”（ $\rm SSAM$ ）。

对称压缩后缀自动机的核心优势是可以向两边加字符。

$|\rm endpos|$ 是好求的，将后缀节点设为 $1$ 然后求后缀树子树和即可，我们可以先通过它求出所有含 $\rm context$ 的节点。

节点之间的对应关系可以简单的做的，对每个结点上的最长串我们求出它第一次出现的位置（正串 $\rm SAM$ ）和最后一次出现的位置（反串 $\rm SAM$ ），使用一个 std::map<pair<int,int>,int> 查询即可，硬用哈希表也不是不能线性。

对称压缩后缀自动机有好的性质。

剩下的性质，留在基本子串结构中探讨。

两边加字符，版本回溯，判断字符串是不是 $S$ （初始给定）的子串。

$n\le 10^6$ 。

只需维护每个版本的串的 $\rm SSAM$ 节点编号，在该节点中的位置，对每个节点求出一组在原串中的出现位置即可。

出边只需记录第一个字符，其实我们还需要记录每个 $\rm context$ 在其后继中的位置，这个需要在缩的过程中记录偏移量。

给定 $S$ ，定义游戏 $T$ 为：给定 $S$ 的子串 $T$ ，两个玩家每次需要在保证 $T$ 是 $S$ 子串的前提下在 $T$ 左右各加一个字符，操作不了的人输。

求先手必胜状态字典序第 $k$ 小的串本质不同子串 $T$ 。

$|S|\le 10^5,k\le 10^{10}$ 。

运用上面提到的性质，只要一个串既不左顶满又不右顶满，它下一步就是固定的，所以我们需要关心的点是左顶满或右顶满的点。

左顶满的点一定是右后缀自动机（正串）的代表节点，右顶满的点一定是左后缀自动机的代表节点，所以需要关心的点有 $\mathcal O(n)$ 个。

我们现在已经会查询每个点是不是必胜了，求字典序第 $k$ 小那我们就遍历正串 $\rm SAM$ ，如何求一个点向后匹配的必胜点数呢？