[string-2]基本子串结构学习笔记

Moeebius · 2024-07-26 21:13:36 · 科技·工程

前置知识：SAM。

免责声明：本文中略过了很多证明。

引入

考虑如下问题：

（杭电多校 2024 第三场 T6）给定一个字符串 S，每次询问一段子串 S[l\dots r]，求：

有多少个本质不同的字符串 T 满足 \text{occ(T)}=\text{occ}(S[l\dots r])，且 S[l\dots r] 是 T 的子串。

有多少个本质不同的字符串 T 满足 \text{occ(T)}=\text{occ}(S[l\dots r])，且 T 是 S[l\dots r] 的子串。

其中 \text{occ}(T) 表示 T 在 S 中的出现次数。

容易想到对于正反串分别建立 SAM，但这样并不是很利于刻画“\text{occ} 等价类”，因为我们并不知道正串 SAM 上的节点跑到反串 SAM 上是哪里。

我们需要一个更有力的、刻画子串的结构。

\text{ext} 等价类与对称压缩 SAM

在思考需要的结构之前，我们要先明确这个所谓的“\text{occ} 等价类”到底长什么样。

Definition 1. 定义 \text{ext}(T) 为极长的串 T' 满足 \text{occ}(T')=\text{occ}(T)，且 T 为 T' 的子串。

可以证明，T' 存在且唯一。（注意到 T' 其实就是正串 SAM 上 T 对应节点中最长串与反串 SAM 对应节点中的最长串拼接而成。）

我们称 T_0,T_1 属于一个等价类，当且仅当 \text{ext}(T_0)=\text{ext}(T_1)。

我们发现 SAM 已经完成了向左扩展的任务。容易注意到，一个节点可以向右扩展，且不改变其出现次数，当且仅当：

它不对应一个后缀。
它在 SAM 上的出边（转移边）只有一条。

于是我们可以将出度为 1 且不代表后缀的点与它出边指向的点合并，得到了一个“双向扩展，单向转移”的结构，我们称之为压缩 SAM。压缩 SAM 上的一个点对应一个 \text{ext} 等价类。

好了我们现在可以合并了，因为 \text{ext} 等价类与这个串是正向的还是反向的没有关系。

叠合正反串压缩 SAM 的对应节点，同时保留对应出边，我们得到了一个支持双向转移的结构——对称压缩 SAM。

听起来很有意思。

阶梯划分，基本子串结构

对称压缩 SAM 只刻画了等价类之间的转移关系，等价类内的关系是混乱的，我们考虑把它画到网格图上。

对于每个子串 S[l\dots r]，我们将其写在 (l,r) 上；对于同一等价类，我们将其染上同一种颜色。

这样得到的结构就称之为（初步的）基本子串结构或者叫“阶梯划分”，每个同色连通块称为一个块。容易发现块与块之间两两不相交；每个子串只会出现在一种颜色的块内。

下图展示了 \mathtt{abbab} 的正反压缩 SAM、对称压缩 SAM 和基本子串结构（图源：字符串技术巡礼）：

下面证明几个重要的性质：

Lemma 1. 每个块是一个阶梯状网格图，且上端和左端对齐。

证明：

首先考虑上端和左端对齐。假设块内有两个点 (l_1,r_1) 和 (l_2,r_2)，那么这两个点的对应的 \text{ext} 是相同的，并且与 (\min(l_1,l_2),\max(r_1,r_2)) 也相同。所以对于每一个块 k 我们有最左上方的点（代表元） \text{rep}(k)，容易发现这个点对应的子串就是这个等价类对应的 \text{ext}。这个点唯一确定了块的上边界和左边界。
“阶梯状”意味着对于 l < l' \le r' < r，都有 (l'-1,r), (l',r+1), (l',r') 在同一块 k 内，其中 \text{rep}(k)=(l,r)。这也是好理解的。

Lemma 2. 每个块 k 恰好出现了 \text{occ}(\text{rep}(k)) 次。块内每个元素（在该块内）恰好出现了 1 次。

证明从略。

Lemma 3. 每个块的每一行唯一对应正串 SAM 中的一个节点，每一列唯一对应反串 SAM 中的一个节点。

证明：注意到每一行对应一个 \text{endpos} 等价类，且其不能向两边扩展。列的情况同理。

这个还引出了下一个重要推论：

Lemma 4. 所有本质不同的块的周长之和为 O(|S|) 量级。

证明：由 Lemma 3 易推得。

DAG 无用论，树边标记

这里咕掉了若干个引理。

考虑走正串 SAM 的 DAG 边的过程：

如果不在等价类边界上，那么仅有一条出边，连向这个位置上方的位置；
否则，会连向所有反串 parent tree 上孩子节点的「对应位置」。

所以正反串的 parent tree 中包含了所有 DAG 的信息。

关于如何找到这个「对应位置」，我们有一种简洁的树边标记方法：

我们预处理出 SAM 上每个点 i 对应 \text{endpos}(i) 集合中的最小值，记为 \text{pos}(i)。

对于 i\rightarrow \text{link}(i) 这条树边，我们可以马上知道 \text{link}(i) 的最长串是通过加上 S_{\text{pos}(i)-\text{len(link(}i))} 得到的！

因此扫一遍便完成了树边标记的任务。

构建算法

假设字符集大小 \Sigma 为常数。

下面给出的是来自 Crashed 的做法而不是原论文做法。

构建正反串的 SAM。这个可以 O(n) 做。
标记代表元。

注意到正串 SAM 上一个节点对应的最长字符串总是落在该块的左边界上。所以我们只需要把左边界对应的反串 SAM 节点拿出来（这是可以唯一确定的），比一比 \text{len}_0(p) 和 \text{len}_1(q) 就好了。

假设我们目前在 p,q 这两个点上；我们枚举正 SAM 的 DAG 上出边，并且我们只走 \text{len}_0(p')=\text{len}_0(p)+1 的出边，这样可以让我们一直在左边界上。

如果当前点不是代表元那么这样往上走是不会改变 q 的；否则我们需要找到 q 在 parent tree 上的哪个孩子是通过这个字符转移到的，这个可以通过上面提到的树边标记预处理。

（必要性证明先咕了。）

另外，如果不要求线性复杂度，我们也可以枚举正 SAM 中的每个节点，定位其第一次出现的位置，然后以一只 \log 的代价找出其在反 SAM 上的对应节点，然后比较他们的 \text{len}；这样做的正确性比较显然。

划分等价类

我们按照 SAM 中 \text{len} 从小往大的顺序扫一遍，如果一个点还未被归入某一个等价类就扫描他 DAG 上的的所有出边（符合条件的一定只有一条），并将其标记为 DAG 出边所指向的等价类。

另外，存在一种“按照 SAM 中编号从大往小扫描”的做法，正确性证明未知。

行列排序

神奇的事情是不用排，3 中倒着扫的时候顺带加入，就天然形成了倒序结构，所以最后形成的顺序就是行从上往下，列从左往右（因为本来是反串，再倒一次就形成了“正序”）。

（证明也咕了。）

应用与例题

对于本文开头提到的问题：

对于询问一，其实就是在询问等价类中，一个点左上方有几个子串（下图中蓝框）。
对于询问二，其实就是询问等价类中，一个点右下方有几个子串（红框）。

\text{Fig 1. 询问子串为 bba 时，答案在网格图上的体现。}

随便拿个啥 DS 维护一下即可。