2026-07-23
对称压缩后缀自动机
考虑 SAM 每个节点的基本结构，本质上就是代表了子串 \([l',r],[l'+1,r]\dots,[l,r]\) 使得这些子串在原串中的出现位置相等. 换句话说，对于任何一个子串 \([x,y]\)，它在自动机上节点的意思就是，我们可以向左扩展得到极大子串 \([x',y]\)，使得其出现位置集合相等.
同理，如果我们使用后缀树的结构，或者建立反向的 SAM，那么我们就可以得到 \([x,y]\) 向右的极大子串扩展 \([x,y']\)，使得其出现位置集合相等.
于是很自然的一个想法就是如何把 SAM 和后缀树的两种压缩给合并到一起，使得 \([x,y]\) 可以向左向右扩展到一个极大子串 \([x',y']\). 我们定义 \(Ext(u)\) 表示往 \(u\) 的向左向右如此扩展到一个极大的子串. \(Ext\) 是良定义的，因为如果 \([a,b],[c,d]\) 出现位置集合相同并且 \(a\le c\le b\le d\) 那么 \([a,d]\) 出现位置集合也一定和他们一样.
于是我们可以用 \(Ext\) 来定义等价类，并且可以用 SAM 的变体来表示. 具体而言就是把后缀树的边压缩给放到 SAM 上，把所有出度为 \(1\) 的边都给缩掉就行了. 这样 SAM 的每一边上写的都是一个串，和后缀树一样. 我们称之为压缩后缀自动机（见下图）.
另一方面，由于 \(Ext\) 的等价关系无关串的正反，所以我们可以对反串也进行相同的操作. 于是两者得到的点（等价类）是一致的，但是边是不同的，分别代表了正向加点和反向加点. 同时保留两个自动机的转移，我们就得到了对称压缩后缀自动机.
基本子串结构
Ext 等价关系并不是一个容易理解或者表达的等价关系. 为了更好表示这个等价关系，我们定义基本子串结构：
- 将 \(u\) 的所有子串画在一个上三角中，横坐标表示左端点，纵坐标表示右端点，并将 Ext 等价的位置染上相同的颜色. 我们把染色连通块看作一个块.
- 于是对称后缀压缩自动机上的每一条边都可以贴到这个上三角网格上作为横着的或者竖着的转移边（见下图）.
性质：
每一个块都满足都满足左边&上边是平直的，右边&下边形成了阶梯.
Proof：左边&上边的形状有 Ext 的良定义直接得到. 而由于块内任何一个点任意向左向上都会走到左上角，所以右下的轮廓一定是阶梯的.
对于一个块 \(C\)，定义其左上角的串为代表串 \(Rep(C)\)（即极大串），于是 \(C\) 在表格中出现次数为 \(occ(Rep(C))\). 这是显然的.
\(C\) 中一行表示一个 SAM 节点，一列表示一个后缀树（反串 SAM）节点.
所有本质不同的 \(C\) 的周长之和为 \(O(|w|)\).