{"ID":2878924,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.17365","arxiv_id":"2508.17365","title":"Better Indexing for Rectangular Pattern Matching","abstract":"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\u003e0$. Further, our structure can be constructed in $\\tilde{\\mathcal{O}}(n)$ time.","short_abstract":"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 assumpt...","url_abs":"https://arxiv.org/abs/2508.17365","url_pdf":"https://arxiv.org/pdf/2508.17365v1","authors":"[\"Paweł Gawrychowski\",\"Adam Górkiewicz\"]","published":"2025-08-24T13:48:43Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}