浅记基本子串结构构建的二三事

这东西真是学一次忘一次，为了不再忘了它也为了之后讲课可能要讲这玩意，所以梳理一下基本子串结构的一些基本逻辑。这不是学习笔记，更类似于提纲，所以讲得比较抽象……QwQ

假设我们不是苛求严谨性的理论计算机科学研究者，而只是一位期望用基本子串结构做做题的一名普通 OIer。那么关于它我们只需要知道如下几个事实：

• 对于两个 \(s\) 子串 \(t_1,t_2\)，如果 \(t_1\) 是 \(t_2\) 的子串，而且每次 \(t_1\) 在 \(s\) 中的出现都是在 \(t_2\) 中出现，那么称 \(t_2\) 为 \(t_1\) 的扩展串。一个字符串拥有的最长扩展串成为其代表元，代表元唯一。

• 将字符串 \(s\) 的所有子串 \(s[l,r]\) 按 \((n-r+1,l)\) 为下标写在二维平面上。则代表元相同的所有字符串形成了一个直角阶梯形。

• 在这个结构中，对于每一个本质不同（代表元代表的串不同而非位置不同）的直角阶梯形，其一行对应着正串 SAM 上的一个节点，一列对应反串 SAM 上的一个节点。

• 基本子串结构与对称压缩后缀自动机结构等价，本质上是刻画正串 SAM 和反串 SAM 之间关系的一个结构。我们知道 SAM 的 link 树刻画了后缀关系，即前面加删字符；转移 DAG 刻画了前缀关系，即后面加删字符。所以在基本子串结构被系统梳理之前，处理这类问题的方法一般是同时处理 DAG 和 link 树，也就是 DAG 链剖分。（如你所见，这种方法既没有体现正与反的优美对称性，而且还极其难写）

• 正串 link 树和反串 DAG 刻画了平面上的左右转移，而反串 link 树和正串 DAG 刻画了平面上的上下转移。

• 如何判断一个串是不是代表元？这等价于其位于其等价类阶梯的左下角。看一下其所在的正串 SAM 节点和反串 SAM 节点的 \(maxlen\) 是否相同即可。

• 所谓的构建基本子串结构，指的实际上是将正串 SAM 节点和反串 SAM 节点分别归类到他们属于的等价类里面去。它不仅得到了正反串 SAM 之间的对应关系，而且还保留 SAM 带给我们的节点之间的联系。

• 值得一提的是，尝试得到正反串 SAM 之间的对应关系早在基本子串结构被系统总结前就已经被运用在做题上了，比如说 ULR#1 打击复读标解的算法七。我们想要在做题中运用基本子串结构，往往也是从正反 SAM 共同考虑入手。

那么如何构建基本子串结构呢？这其实是有两个层次的，对于大多数的题目，比如说 CF1817F，我们实际上根本不需要建反串 SAM，只需要知道正串 SAM 中的哪些节点属于同一个等价类。

这个时候我学习的是 Kubic 的想法，我们只需要压缩正串 SAM 的 DAG 使其成为压缩后缀自动机。方法是如果一条 DAG 转移边两边 \(\text{endpos}\) 集合大小相同，称这条边是好的。容易发现如果只保留好的边，原图变成了若干条链，每一条链都对应着一个等价类。由于同一个等价类中一定是 \(maxlen\) 小的 SAM 节点先被标号，所以说直接按标号从小到大 dfs 好的边就完成了构建。

还有一些题目，需要你完整的指出一个正串 SAM 节点对应着哪一个反串 SAM 节点。一种方法是延续上面的想法，建完正反 SAM 后分别归类。然后再寻找正反 SAM 上的等价类之间的对应，方法是求出代表元。这里可能需要写一些哈希表之类的用来归类。

有没有办法边归类边寻找正反串 SAM 的对应关系呢？我们考虑保留正 SAM 转移图中 \(maxlen_v=maxlen_u+1\) 这样的转移边 \((u,v)\)，称其为“连续的”转移边。可以发现从空节点开始只走连续转移边一样能遍历到所有节点，而且如果在基本子串结构上看，我们相当于是一直走在一个等价类的第一列！那么我们可以开始不断沿连续边 dfs，如果 dfs 到了一个代表元节点，再往后 dfs 就需要更新当前节点所对应的反 SAM 节点，在反 SAM 的后缀树上找到对应转移边字符的儿子即可。

此时对应的反串 SAM 节点相同的正串 SAM 节点自然归入了一类。