Searching 2D-Strings for Matching Frames
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911845109989376 |
|---|---|
| author | Boneh, Itai Fried, Dvir Golan, Shay Kraus, Matan Miclaus, Adrian Shur, Arseny |
| author_facet | Boneh, Itai Fried, Dvir Golan, Shay Kraus, Matan Miclaus, Adrian Shur, Arseny |
| contents | We introduce the natural notion of a matching frame in a $2$-dimensional string. A matching frame in a $2$-dimensional $n\times m$ string $M$, is a rectangle such that the strings written on the horizontal sides of the rectangle are identical, and so are the strings written on the vertical sides of the rectangle. Formally, a matching frame in $M$ is a tuple $(u,d,\ell,r)$ such that $M[u][\ell ..r] = M[d][\ell ..r]$ and $M[u..d][\ell] = M[u..d][r]$.
In this paper, we present an algorithm for finding the maximum perimeter matching frame in a matrix $M$ in $\tilde{O}(n^{2.5})$ time (assuming $n \ge m)$. Additionally, for every constant $ε> 0$ we present a near-linear $(1-ε)$-approximation algorithm for the maximum perimeter of a matching frame.
In the development of the aforementioned algorithms, we introduce inventive technical elements and uncover distinctive structural properties that we believe will captivate the curiosity of the community. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_02670 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Searching 2D-Strings for Matching Frames Boneh, Itai Fried, Dvir Golan, Shay Kraus, Matan Miclaus, Adrian Shur, Arseny Data Structures and Algorithms We introduce the natural notion of a matching frame in a $2$-dimensional string. A matching frame in a $2$-dimensional $n\times m$ string $M$, is a rectangle such that the strings written on the horizontal sides of the rectangle are identical, and so are the strings written on the vertical sides of the rectangle. Formally, a matching frame in $M$ is a tuple $(u,d,\ell,r)$ such that $M[u][\ell ..r] = M[d][\ell ..r]$ and $M[u..d][\ell] = M[u..d][r]$. In this paper, we present an algorithm for finding the maximum perimeter matching frame in a matrix $M$ in $\tilde{O}(n^{2.5})$ time (assuming $n \ge m)$. Additionally, for every constant $ε> 0$ we present a near-linear $(1-ε)$-approximation algorithm for the maximum perimeter of a matching frame. In the development of the aforementioned algorithms, we introduce inventive technical elements and uncover distinctive structural properties that we believe will captivate the curiosity of the community. |
| title | Searching 2D-Strings for Matching Frames |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2310.02670 |