Approximate Cartesian Tree Matching: an Approach Using Swaps
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912075653054464 |
|---|---|
| author | Auvray, Bastien David, Julien Groult, Richard Lecroq, Thierry |
| author_facet | Auvray, Bastien David, Julien Groult, Richard 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 algorithm for solving approximate Cartesian tree pattern matching. We consider Cartesian tree pattern matching with one swap: given a pattern of length m and a text of length n we present two algorithms that find all the factors of the text that have the same Cartesian tree of the pattern after one transposition of two adjacent symbols. The first algorithm uses a characterization of a linear representation of the Cartesian trees called parent-distance after one swap and runs in time Theta(mn) using Theta(m) space. The second algorithm generates all the parent-distance tables of sequences that have the same Cartesian tree than the pattern after one swap. It runs in time O((m^2 + n)log m) and has O(m^2) space complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_16065 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Approximate Cartesian Tree Matching: an Approach Using Swaps Auvray, Bastien David, Julien Groult, Richard 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 algorithm for solving approximate Cartesian tree pattern matching. We consider Cartesian tree pattern matching with one swap: given a pattern of length m and a text of length n we present two algorithms that find all the factors of the text that have the same Cartesian tree of the pattern after one transposition of two adjacent symbols. The first algorithm uses a characterization of a linear representation of the Cartesian trees called parent-distance after one swap and runs in time Theta(mn) using Theta(m) space. The second algorithm generates all the parent-distance tables of sequences that have the same Cartesian tree than the pattern after one swap. It runs in time O((m^2 + n)log m) and has O(m^2) space complexity. |
| title | Approximate Cartesian Tree Matching: an Approach Using Swaps |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2306.16065 |