Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.09236 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912375816323072 |
|---|---|
| author | Auvray, Bastien David, Julien Ghazawi, Samah Groult, Richard Landau, Gad M. Lecroq, Thierry |
| author_facet | Auvray, Bastien David, Julien Ghazawi, Samah Groult, Richard Landau, Gad M. Lecroq, Thierry |
| contents | Cartesian tree pattern matching consists of finding all the factors of a text that have the same Cartesian tree than a given pattern. There already exist theoretical and practical solutions for the exact case. In this paper, we propose the first algorithms for solving approximate Cartesian tree pattern matching with one difference given a pattern of length m and a text of length n. We present a generic algorithm that find all the factors of the text that have the same Cartesian tree of the pattern with one difference, using different notions of differences. We show that this algorithm has a O(nM) worst-case complexity and that, for several random models, the algorithm has a linear average-case complexity. We also present an automaton based algorithm, adapting [PALP19], that can be generalized to deal with more than one difference. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_09236 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximate Cartesian Tree Matching with One Difference Auvray, Bastien David, Julien Ghazawi, Samah Groult, Richard Landau, Gad M. Lecroq, Thierry Data Structures and Algorithms Cartesian tree pattern matching consists of finding all the factors of a text that have the same Cartesian tree than a given pattern. There already exist theoretical and practical solutions for the exact case. In this paper, we propose the first algorithms for solving approximate Cartesian tree pattern matching with one difference given a pattern of length m and a text of length n. We present a generic algorithm that find all the factors of the text that have the same Cartesian tree of the pattern with one difference, using different notions of differences. We show that this algorithm has a O(nM) worst-case complexity and that, for several random models, the algorithm has a linear average-case complexity. We also present an automaton based algorithm, adapting [PALP19], that can be generalized to deal with more than one difference. |
| title | Approximate Cartesian Tree Matching with One Difference |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.09236 |