我们研究了内部字典匹配（IDM）问题，该问题给定一个包含 $d$ 个子字符串的字典 $\mathcal{D}$ 和文本 $T$，每个查询涉及在 $T$ 的另一个子字符串中寻找 $\mathcal{D}$ 中模式的出现情况。我们提出了一种新的 $O(n)$ 大小的数据结构，称为基本子字符串结构（BASS），其中 $n$ 是文本 $T$ 的长度。利用 BASS，我们能够在近乎最优的查询和预处理时间内处理 IDM 问题的所有类型查询。具体而言，我们的结果包括：
- 首个算法能够以 $\tilde{O}(1)$ 时间回答 CountDistinct 查询，预处理时间为 $\tilde{O}(n+d)$，其中我们需要计算在 $T[l,r]$ 中存在的不同模式的数量。之前的最佳结果是在 $\tilde{O}(m)$ 时间内每个查询，预处理时间为 $\tilde{O}(n^2/m+d)$ 或 $\tilde{O}(nd/m+d)$，其中 $m$ 是一个选择的参数。
- 对于其他两种内部查询类型，我们也提供了更快的算法。我们将（1）发生计数（Count）查询的运行时间提升至每个查询 $O(\log n/\log\log n)$，预处理时间为 $O(n+d\sqrt{\log n})$，而之前是每个查询 $O(\log^2 n/\log\log n)$，预处理时间为 $O(n\log n/\log \log n+d\log^{3/2} n)$；（2）不同模式报告（ReportDistinct）查询的运行时间降至每个查询 $O(1+|\text{output}|)$，而之前为 $O(\log n+|\text{output}|)$。此外，我们在其他两种查询类型，模式存在（Exists）和发生报告（Report）中也达到了最优运行时间。我们还表明，BASS 更广泛适用于其他内部查询问题。
博主点评： BASS 数据结构的提出代表了对内部字典匹配问题的重大突破，它不仅在理论上提供了近乎最优的时间复杂度，还在实践中展现了强大的适用性。这为处理大规模文本数据提供了新思路，尤其是在需要频繁查询的应用场景中。其高效的预处理和查询时间将极大提升文本检索的性能。