Better Indexing for Rectangular Pattern Matching
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918129835180032 |
|---|---|
| author | Gawrychowski, Paweł Górkiewicz, Adam |
| author_facet | Gawrychowski, Paweł Górkiewicz, Adam |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_17365 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Better Indexing for Rectangular Pattern Matching Gawrychowski, Paweł Górkiewicz, Adam Data Structures and Algorithms 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. |
| title | Better Indexing for Rectangular Pattern Matching |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.17365 |