Cartesian Forest 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_ | 1866911215721119744 |
|---|---|
| author | Auvray, Bastien David, Julien Groult, Richard Lecroq, Thierry |
| author_facet | Auvray, Bastien David, Julien Groult, Richard Lecroq, Thierry |
| contents | In this paper, we introduce the notion of Cartesian Forest, which generalizes Cartesian Trees, in order to deal with partially ordered sequences. We show that algorithms that solve both exact and approximate Cartesian Tree Matching can be adapted to solve Cartesian Forest Matching in average linear time. We adapt the notion of Cartesian Tree Signature to Cartesian Forests and show how filters can be used to experimentally improve the algorithm for the exact matching. We also show a one to one correspondence between Cartesian Forests and Schröder Trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_02704 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cartesian Forest Matching Auvray, Bastien David, Julien Groult, Richard Lecroq, Thierry Data Structures and Algorithms In this paper, we introduce the notion of Cartesian Forest, which generalizes Cartesian Trees, in order to deal with partially ordered sequences. We show that algorithms that solve both exact and approximate Cartesian Tree Matching can be adapted to solve Cartesian Forest Matching in average linear time. We adapt the notion of Cartesian Tree Signature to Cartesian Forests and show how filters can be used to experimentally improve the algorithm for the exact matching. We also show a one to one correspondence between Cartesian Forests and Schröder Trees. |
| title | Cartesian Forest Matching |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.02704 |