BASS-一种用于处理区间匹配问题的字符串数据结构

· · 算法·理论

BASS（Basic Substring Structure） 是一种字符串数据结构，善于处理区间模式串匹配的相关问题。它由两个 IOI 金牌和他们的导师共五位作者（\%\%\%，其中一个曾获得 ～580pts 的好成绩）于 2023.12 及之前在一篇论文 Nearly Optimal Internal Dictionary Matching 中提出。

必须的前置知识：普及算法基础、SAM 及其简单应用（需要对其功能有一定的理解，本文不介绍，请移步 OI-wiki——当然不排除之后出文章的可能性）、二维偏序（离线排序+树状数组）……

它能解决的一个问题：给定文本串和模式串集，q 次区间询问求区间内一共有多少次匹配，同一模式串多次出现则重复计数。

如果你不感兴趣或没有前置知识，现在可以划走了。

目录与约定

简单介绍一下本文的结构，让我们能有一个清晰的地图。

本文共五章，分为：

下面我们用 S 来表示我们需要构建 BASS 的原串，并使用 1-based 刻画下标。

代表元

BASS 将记录一组性质相似的子串压缩为只记录一个代表元。

先形象地概述一下“代表”是什么：每一个 x 的出现，都可以通过在前面和后面添加相同的字符，来一一对应一个 y 的出现。此时我们认为 y 可以代表 x。

具体地，考虑现在我们有一个子串 x=S[l:r]，需要获取它的代表元。

我们考虑这样一个的扩张过程用来获取代表元：

为什么只要看出现次数呢？因为扩张一步只可能让新串的出现次数减少，不会增多，那如果没有减少，并且要扩张的字母都相同，就说明可以建立一个从原串出现到新串出现的一一映射，符合定义。

容易发现顺序其实是没关系的，而且无论按什么顺序扩张，最后都会得到相同的结果 y，并且每个扩张的中间过程中的 x' 的代表元也必定是最终的 y。

这是因为，一次有效的向右扩展会保留每个出现及其起始位置。这些信息全是右侧的，对左侧没有影响——所以它不能改变哪些向左扩展是有效的。另一侧是对称的。

我们找到所有子串的代表，这样形成的代表关系传递后会形成若干个连通块，我们简称为“块”。对于每个块，我们取代表关系的根节点作为代表元。

总结一下：

一个块内的所有子串出现“位置”在某种意义上相同。可以通过向左向右扩张的方式找到一个块的代表元。

BASS 在做什么

接下来我们要利用这个压缩信息。

为了调动几何直观，想象我们在一张网格图上。横坐标是子串的起点，升序排列；纵坐标是子串的终点，降序排列。

其中同一个颜色代表了一个块。注意：一个块会在棋盘格中出现很多次，由于每个块代表的字符串是相同的，对于每个块我们可以只计算一遍，并且很多时候只和它的行数 + 列数相关（而不是 \times）。这是优化复杂度的关键。它可以将很多 O(n^2) 的问题压缩到 O(n)。

那么我们一次向左扩张其实就是在网格图上向左走一步。一次向右扩张就是在网格图上向上走一步。

我们刚才寻找代表元的过程就是先向左走，再向上走，最终走到一个方格。

由于顺序是无关的，我们知道每个点向上和向左一直到代表元的区域（一个矩形）都是这个代表元的块内区域。因此我们可以知道，一个块的形状是一个阶梯状物。

我们可以记录每个块的形状信息，来避免记录它的所有面积（那会是 O(n^2) 的）。

接下来的部分，我们将解决：如何获取每个块的信息，以及如何证明这些信息总和是 O(n) 的。

总结一下：

所有块构成的“楼梯”可以在网格上拼成所有子串。我们只需要记录块的形状信息。

获取块的信息

我们考虑一下如何证明所有本质不同的块的行数和列数相加是 O(n) 的。

再看一下这张图：

我们考虑刚才那个扩张过程。我们把它用更简化的表述 copy 过来：

并且向左和向右扩张的步数对应了，我们的出发点到代表元的格子在网格上，需要向左和向上走的步数。

既然是左侧和右侧，很容易想到对称。具体地，当我们做完向左扩张之后，只要对应到反串上再做一次“向左扩张”就能得到完整的代表元。

我们考虑向左扩张过程中得到的这些字符串都有什么共同点。

因为只向左扩张，且维持计数不变，所以它们的出现在原串中的结束位置集合都是相同的。

那跟“出现结束位置集合”endpos 有关的数据结构是什么？当然是 SAM。

我们对正串建 SAM，然后只需要找到 S[l:r] 所对应的状态。它就代表了所有和它 endpos 集合相同的子串。

因此，我们注意到，所有块的每一行都一一对应一个正串 SAM 状态。因此所有行数的和是 O(n) 的。

那么同理，所有块的每一列都一一对应一个反串 SAM 状态（它们的开始位置集合相同）。因此所有列数的和也是 O(n) 的。

因此行列数的和是 O(n) 的。

一个额外的性质是：每个块中某个状态，其向左的块的同一行状态（容易发现最多只有一个）的正串后缀链接树祖先就是这个状态。列方向在反串上同理。

至此我们完成了数量上的证明，考虑如何实现获取块的形状信息——它已经呼之欲出。

插播一个问题：如何快速获取某一个子串的代表元？

我们先向左扩张。

找到该子串对应的 SAM 状态。然后我们只需要找到其中最长的字符串的长度（也就是 SAM 中维护的 \operatorname{maxlen}），就完成了向左扩张。因为这个最长的字符串就是向左扩张后的结果。

那么如何找这个状态呢？我们从左到右遍历一遍原串，预处理出每个前缀字符串所对应的 SAM 状态，那么 S[l:r] 的对应状态在后缀链接树中必然是 S[1:r] 的祖先。并且这个祖先的长度范围要包含 r-l+1。

那么这就好做了，我们只需要倍增找第一个 minlen\le r-l+1 的祖先就好了。

对右边做一遍相同操作

这样扩展是 O(\log n) 的单次的，但它支持在线查询。

既然每行每列都对应一个 SAM 状态，那我们不妨考虑直接反向从 SAM 状态出发构造所有块。

再次拿出这张图方便结合几何直观思考：

我们 dfs 正串的后缀链接树（这会在同一行内按照先右后左的顺序遍历），得到一个 SAM 状态的时候，我们只要知道它属于哪个块，我们就能把它加入到那个块的行列表。然后最后遍历所有块按照块内 \operatorname{maxlen}（因为注意到同一个块内上方的行 \operatorname{maxlen} 较大）进行排序即可。

这当然可以用前面的问题进行 O(n\log n) 构建，具体地，只需要额外记录，该状态包含的最长子串，第一次出现的结束位置。这样就可以得到一个具体的子区间，对应最长子串。

但是我们也可以不用前面的问题得到更优的复杂度。

还是考虑那个扩张过程：

如果我们使用正串 SAM，我们现在能知道的是如何向左扩张，也就是所有块的行的集合。但是我们并不知道哪个行对应哪个块。这需要把向右也补齐。

向右就是在该状态的每个字符串的右边都加同一个字母，并保持出现次数不变，比如上图中最左上角的块的行 4 到行 5 就是每个字符串都加了一个 a。这在 SAM 中对应什么？当然是字符转移。

因此我们得到了两个相邻行属于同一块的充要条件：存在从状态 u\to v 的字符转移，并且两者的出现次数相等。

我们很容易在 SAM 上维护每个节点的“出现次数”。每个新建的状态初始计数为 1；每个克隆状态初始计数为 0。然后按 \operatorname{maxlen} 递减处理状态，把每个状态的计数加到其后缀链接父结点上就可以。

那么我们直接维护块编号就可以。具体地：

我们按 \operatorname{maxlen} 递减的顺序处理所有 SAM 状态（同 \operatorname{maxlen} 顺序无关）。

遍历每个状态的所有字符转移，如果存在某个转移使得两者计数相等，就把先该状态的块编号设为与转移到的点相等，再将状态加入对应块。否则就将块编号设为状态的编号（或者任何值域为 n 的不重复的值）。

最后遍历所有块编号就能得到所有块，并且根据我们的处理顺序，它们已经天然按 \operatorname{maxlen} 排好序。

对于状态 u 对应的行，其宽度为

1\le x\le \operatorname{maxlen}(u)-\operatorname{maxlen}(\operatorname{link}(u))

因而处理所有状态后，我们就得到了整个块的形状。

这样显然是 O(\Sigma\cdot n) 的。

但是如果我们也需要所有的反串 SAM 状态，那怎么办呢？

可以先对反串跑一遍刚才的算法，这样我们就能以列的形式得到所有块。

考虑如何进行配对——我们需要不变量。注意到每个块的代表元不管怎么表示都是相同的。

因此，我们记录所有代表元在原串中第一次出现的起始点和结束点（在反串上就是最后一次）。

我们按起始点进行桶排序，然后每层先把行 SAM 的结束点赋值成对应状态，再遍历列 SAM 合并一下就可以了。

并不需要清空，因为被读到的状态必然存在在同一层，直接覆写就可以了。

总结一下，这个部分最重要的核心思想是：

每个块的每行每列都对应一个 SAM 状态。

应用

接下来，我们看看 BASS 能用来解决什么问题。

典型的是有关区间匹配的一类问题。当然由于本人能力不足也可能没将 BASS 开发完。

先考虑两个基础问题：

给定长度为 n 的文本串，以及总长度为 m 的模式串集。对于 q 次区间询问，求：

  • 区间内一共有多少次匹配，同一模式串多次出现则重复计数；
  • 区间内出现了多少种模式串，同一模式串只计一次。

当然我们将不会在本文中（或许在后续文本中）给出第二种的解法，因为它将涉及到可持久化线段树和 LCT，而后者可能对大部分读者来说并不熟悉，写了也没人看。

那么如何解决第一个问题呢？个人推荐可以先思考一会儿。这将不会用到很超标的算法。

或者答案就在下面，准备好了就可以看：

还记得前面说过的吗？

同一个块的不同副本，包含的是同一组字符串。因此，我们只需要计算其中一个副本。

具体到这个问题上：两个区间只要对应的字符串相同，其中包含的模式串匹配次数就一定相同。因此，同一个块的对应格子可以共用答案。

令 w(l,r) 表示 S[l:r] 是否属于模式串集：属于则为 1，否则为 0。令 F(l,r) 表示区间 [l,r] 内的匹配总次数。

一个匹配 [i,j] 被询问区间 [l,r] 完全包含，当且仅当

l\le i\le j\le r.

在之前的网格图中，这些格子恰好位于询问格子的右下方，包含正右方、正下方和询问格子本身。

不信再看一遍：

因此

F(l,r)=\sum_{l\le i\le j\le r}w(i,j).

这就是一个二维数点问题。

但我们不能直接把所有匹配位置都放到平面上：匹配总数可能达到 O(n^2)。BASS 的作用，就是让我们按块处理，复用不同副本之间的计算结果。

对于每个模式串，只需找到它所属的块（直接在 SAM 上沿字符转移走就好了）和块内位置，在那里记录一个标记；不必枚举它在文本中的所有出现。对于每个询问，也使用一样的方法，将它放入对应块中。

现在考虑如何处理一个块。

我们希望处理它时，右侧和下侧相邻块中需要用到的答案都已经算好了。这样，当前块之外的贡献就可以通过边界传进来。

不过，这里有一个容易漏掉的问题：边界上已有的答案，不能直接当成点权相加。

例如，文本为 aaa，模式串只有 a。区间 [1,2] 和 [2,3] 的答案都是 2，但 [1,3] 的答案是 3，而不是 4。直接相加会把中间那个 a 算两遍。

它们在图上看起来像这样：

所以我们需要容斥：

F(l,r)=F(l+1,r)+F(l,r-1)-F(l+1,r-1)+w(l,r).

前两项分别统计去掉左端点、去掉右端点后的匹配；第三项减去重复统计的部分。只有恰好占满整个区间的匹配没有被前两项覆盖，由 w(l,r) 补上。空区间的答案规定为 0。

接下来，只要把这个递推式中的块外贡献移进块内，就能得到我们需要的二维数点。

具体地，为当前块内的格子 (l,r) 设置一个临时点权 a(l,r)，初始为 w(l,r)，然后：

这么做的实际意义是，我们把块外贡献折算到边界格子上。有些区域会被两处边界同时计入，因此还需要在阶梯拐角处减去一次。把这些贡献染色，就能看到容斥是怎么发生的：

这样就很容易理解，所有块外贡献都已经被计入临时点权。之后只在当前块内做二维求和，就能得到正确答案：

F(l,r) = \sum_{\substack{(i,j)\text{ 在当前块内}\\i\ge l,\ j\le r}} a(i,j).

为什么这样做可行？

把块外的 F 值暂时置为 0，临时点权恰好补回了递推式中被去掉的项。因此块内仍然满足原来的递推关系，二维求和便能恢复答案。

并且注意到只有模式串所在的格子，以及紧邻块外的边界格子（包含凹角处的格子，即与外界共点也算），才可能产生非零点权。因此总体非空格子数量可控。

还有两个实现问题：按什么顺序处理块，以及从哪里取得边界答案。

一个方便的处理顺序是：按块中字符串在文本里的出现次数，从大到小处理。

为什么？向右或向下走的时候，相当于不停删掉端点字符，字符串变短，出现次数只会变多。如果次数不变，这次删除对应一次合法扩展的逆操作，因此仍然属于同一个块。

所以，只要走到了另一个块，出现次数就一定严格增加。

这说明，按出现次数从大到小处理时，当前块依赖的块外答案一定已经算好。

此时行、列对应的后缀链接也能帮助我们找到相邻块的所有状态，我们可以在这些 SAM 状态编号上记录对应的答案（显然对于行状态是最左边的格子，列是最上面的），从而快速得到边界。

具体地，任选一个格子，它在图上看起来应该像这样：

为了便于实现，可以在所有边界格子上也挂一个询问，然后给询问一个 val& ans 引用到需要的位置。所有块的边界总规模是 O(n)，所以这类询问也总共只有 O(n) 个。

这样，每个块处理时的逻辑就统一了。

至此，每个块的问题就明确了：

已知若干带权点，回答若干右下方区域求和询问。

这是一个二维偏序板子，使用树状数组足矣。由于所有块的周长之和为 O(n)，很容易在这一部分做到 \sim O\bigl(n\log n\bigr) 的复杂度。

结语

这是一篇抢先文（虽然已经几年了还没人发现这个东西说明热度不大），有不足大家可以提出。

之后可能会更新一篇 BASS 的拓展。给一个模板代码、讲一些更有趣的问题。

或者大家想的话，也可以评论一些好玩的算法，我也可以看看（当然不一定能看懂就是了）。

评论以让我知道你在想什么……当然我更新很懒就是了。