Better Indexing for Rectangular Pattern Matching

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.