技术摘要：近乎最优的内部字典匹配

问题定义

本文研究了内部字典匹配 (Internal Dictionary Matching, IDM) 问题。在该设定中，给定一个长度为 $n$、基于线性可排序字母表的长文本 $T$。字典 $D$ 由 $d$ 个 $T$ 的子串组成。目标是预处理 $T$ 和 $D$，以便高效地回答关于 $D$ 中的模式在 $T$ 的任意子串 $T[l, r]$ 中出现情况的查询。

本文重点关注五种特定的查询类型：

1. Exists($l, r$)： 判断是否至少有一个来自 $D$ 的模式出现在 $T[l, r]$ 中。
2. Report($l, r$)： 报告来自 $D$ 的所有模式在 $T[l, r]$ 中的所有出现位置。
3. ReportDistinct($l, r$)： 报告出现在 $T[l, r]$ 中的所有来自 $D$ 的不同（不重复）模式。
4. Count($l, r$)： 计算来自 $D$ 的所有模式出现的总次数。
5. CountDistinct($l, r$)： 计算出现在 $T[l, r]$ 中的不同模式的数量。

该问题推广了经典的字典匹配和内部模式匹配 (IPM)。它特别适用于“内部”字典，即模式的总长度 $L$ 远大于模式数量 $d$ 的情况（例如，由所有回文串、平方串或非原初子串组成的字典），因为其解决方案的复杂度应取决于 $n$ 和 $d$，而非 $L$。

方法论：基础子串结构 (BASS)

本文的核心贡献是提出了一种名为基础子串结构 (Basic Substring Structure, BASS) 的新型 $O(n)$ 大小的数据结构。BASS 通过二维网格和等价类来组织 $T$ 的子串。

1. 网格与等价类

该结构将每个子串 $T[l, r]$ 映射到二维网格上的一个点 $(l, r)$。

• 等价类： 两个子串是等价的，如果它们的“扩展”相同。子串 $t$ 的扩展记作 $ext(t)$，是指满足$t$是$s$的子串且$|occ(t)| = |occ(s)|$的最长字符串$s$。这一概念对应于紧凑无环词图 (Compact Acyclic Word Graph, CDAWG) 中的节点。
• 块 (Blocks)： 在网格中，每个等价类形成一个具有阶梯状形状的“块”。一个块 $B$ 由参数定义：行范围 $[left_B, right_B]$，顶边界 $top_B$，以及一个非递减的底边界序列 $b_{left_B}, \dots, b_{right_B}$。
• 性质： 本文证明了同一等价类中的所有块在形状上都是一致的（仅差平移）。此外，所有不同块的左边界和顶边界长度之和为 $O(n)$。

2. 树映射

BASS 集成了两种修改后的后缀树，以形式化块之间的关系：

• PreTree($T$)： $T$ 的后缀树。它捕捉共享同一列的块之间的关系（祖先-后代关系）。
• SufTree($T$)： 反转字符串 $rev(T)$ 的后缀树。它捕捉共享同一行的块之间的关系。
  这些树允许该结构高效地将网格坐标映射到节点，从而实现 $O(1)$ 时间定位一个子串的等价类及其在块中的位置。

3. 查询处理策略

• 计数查询 (Count Queries)： 算法将计数问题归约为二维范围计数问题。通过存储沿块边界的模式出现部分的累加和，并利用静态二维范围计数数据结构（基于 Chan 和 Pătraşcu 的工作），优化了查询时间。
• 不同模式计数查询 (CountDistinct Queries)： 这是最复杂的查询。作者将问题分解为两部分：
  1. 计算总出现次数 ($A_1$) 减去由“关键位置”（出现在 $T[l, r]$ 中的最短后缀）决定的特定后缀范围内的出现次数。
  2. 根据后缀 trie 的结构减去过度计算的模式 ($A_2$)。
     为了高效处理此问题，本文引入了源自 Link-Cut Tree 的事件集 (event sets)，用于追踪随着查询范围移动时出现次数的变化，从而利用持久化数据结构计算 $A_2$。

关键结果与贡献

本文提出的算法在所有五种查询类型上均实现了近乎最优的查询和预处理时间。结果汇总如下（其中 $\tilde{O}$ 省略了多项对数因子）：

查询类型	预处理时间	查询时间	空间
Exists	$O(n + d)$	$O(1)$	$O(n + d)$
Report	$O(n + d)$	$O(1 + x)$	$O(n + d)$
Count	$O(n + d\sqrt{\log n})$	$O(\frac{\log n}{\log \log n})$	$O(n + d)$
ReportDistinct	$O(n \log n + d)$	$O(1 + x)$	$O(n + d)$
CountDistinct	$O(n \log^2 n + d\sqrt{\log n})$	$O(\log n)$	$O(n \log^2 n + d)$

注：$x$ 表示输出长度。

具体改进

1. CountDistinct： 本文通过提供第一个能在 $\tilde{O}(n+d)$ 预处理下以 $\tilde{O}(1)$（具体为 $O(\log n)$）时间回答 CountDistinct 查询的算法，解决了前人工作 [16] 中的一个开放问题。之前的最优结果需要 $\tilde{O}(m)$ 查询时间及 $\tilde{O}(n^2/m + d)$ 预处理时间。
2. Count： 查询时间从 $O(\frac{\log^2 n}{\log \log n})$ 提升至 $O(\frac{\log n}{\log \log n})$，作者证明了对于大小为 $\tilde{O}(n)$ 的数据结构，这是基于二维范围计数的下界所达到的最优解。
3. ReportDistinct： 查询时间从 $O(\log n + x)$ 提升至 $O(1 + x)$。
4. 通用适用性： 作者展示了 BASS 可以应用于其他内部查询问题，如区间最长公共子串 (Range Longest Common Substring, RLCS) 问题，实现了 $O(1)$ 查询时间和 $O(n)$ 预处理时间，优于之前的 $O(\log n)$ 查询时间。

重要性与声明

本文声称 BASS 是第一个能够以近乎最优的查询和预处理时间处理所有类型 IDM 查询的数据结构。与以往将不同查询类型视为独立、不相干的处理方式不同，BASS 提供了一个统一的框架。

该工作的意义在于：

• 最优性： 匹配了动态字典匹配已知的条件下界（最高至次多项式因子），并证明了 Count 查询的无条件最优性。
• 统一框架： 成功地将等价类组织到二维网格结构中，架起了 CDAWG 概念与高效子串查询之间的桥梁，而这一联系在先前的文献中未被充分探索。
• 处理大规模字典： 提供了复杂度取决于模式数量 $d$ 而非总长度 $L$ 的解决方案，使其适用于复杂的内部字典（如所有回文串或平方串）。

作者指出，对于动态字典（模式可以添加或删除），他们可以构建在 $\tilde{O}(n^\alpha)$ 时间内处理更新并在 $\tilde{O}(n^{1-\alpha})$ 时间内回答 CountDistinct 查询的算法，这与该设定下的已知条件下界相匹配。