标题： 更优的矩形模式匹配索引 显示英文标题

标题： Better Indexing for Rectangular Pattern Matching

摘要： 我们重新研究了在给定一个大小为$n$的二维字符串的情况下，构建一个索引结构的复杂性，该结构允许定位大小为$m$的二维模式的所有$k$次出现。 虽然在假设模式为正方形的额外条件下，已知该问题的结构大小为$\mathcal{O}(n)$且查询时间为$\mathcal{O}(m+k)$[Giancarlo, SICOMP 1995]，但一种普遍的观点认为，对于矩形模式，由于对某种自然类方法的一个下界 [Giancarlo, WADS 1993]，无法达到这样的（或甚至类似的）界限。 我们证明，事实上，可以构造一个大小为$\mathcal{O}(n\log n)$的非常简单的结构，该结构对于任何矩形模式在$\mathcal{O}(m+k\log^{\varepsilon}n)$时间内支持此类查询，对于任何$\varepsilon>0$。此外，我们的结构可以在$\tilde{\mathcal{O}}(n)$时间内构造。 显示英文摘要

摘要： We revisit the complexity of building, given a two-dimensional string of size $n$, an indexing structure that allows locating all $k$ occurrences of a two-dimensional pattern of size $m$. While a structure of size $\mathcal{O}(n)$ with query time $\mathcal{O}(m+k)$ is known for this problem under the additional assumption that the pattern is a square [Giancarlo, SICOMP 1995], a popular belief was that for rectangular patterns one cannot achieve such (or even similar) bounds, due to a lower bound for a certain natural class of approaches [Giancarlo, WADS 1993]. We show that, in fact, it is possible to construct a very simple structure of size $\mathcal{O}(n\log n)$ that supports such queries for any rectangular pattern in $\mathcal{O}(m+k\log^{\varepsilon}n)$ time, for any $\varepsilon>0$. Further, our structure can be constructed in $\tilde{\mathcal{O}}(n)$ time.