摘要
上下文模式匹配是一个任务，给定一个模式 $P[1,m]$、一个上下文长度 $\lambda$ 和一个文本 $T[1,n]$，需要找到所有 $occ$ 个不同的上下文，其中 $P$ 出现在 $T$ 中。上下文由出现位置前后的 $\lambda$ 个符号组成；必须输出每个上下文出现的位置。
虽然该问题可以使用 $O(n)$ 空间的预处理数据结构以最优时间 $O(m+occ)$ 解决，但在大型重复文本集合中，这种 $O(n)$ 的空间开销可能是不可接受的。我们提出了第一个在压缩空间中运行的最优时间解决方案，即文本 $T$ 的对称压缩有向无环图（SCDAWG）。
此外，我们展示了如何在 $O(m)$ 时间对模式 $P$ 进行预处理后，以 $O(\log\log\lambda)$ 的延迟枚举 $occ$ 个解集。为此，我们开发了一种改进的线性空间距离敏感加权祖先数据结构。
博主点评： 该研究在处理大型重复文本时提供了一种高效的上下文模式匹配方法，利用压缩空间的优势，显著降低了空间复杂度。通过引入对称压缩有向无环图，研究者有效地解决了传统方法的局限性，展示了在实际应用中的潜力。这种创新性的方法有望在信息检索领域得到广泛应用。