Abstract
The Cartesian tree of a string is a binary tree, which is useful in capturing minimalities within strings. We study the approximate pattern matching problem for two Cartesian trees of two strings. We design a poly-time algorithm that computes the minimum edit cost when a given string is edited to match the Cartesian tree of the other string. Then, we adapt the algorithm to the approximate pattern matching problem, where we find all substrings of a given text that match a given Cartesian tree pattern within a given number of edit operations. We also consider variant problems such as the approximate Cartesian matching under Hamming distance, and present poly-time algorithms for the considered problems.
Original language | English |
---|---|
Title of host publication | Developments in Language Theory - 28th International Conference, DLT 2024, Proceedings |
Editors | Joel D. Day, Florin Manea |
Publisher | Springer Science and Business Media Deutschland GmbH |
Pages | 189-202 |
Number of pages | 14 |
ISBN (Print) | 9783031661587 |
DOIs | |
Publication status | Published - 2024 |
Event | 28th International Conference on Developments in Language Theory, DLT 2024 - Göttingen, Germany Duration: 2024 Aug 12 → 2024 Aug 16 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 14791 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 28th International Conference on Developments in Language Theory, DLT 2024 |
---|---|
Country/Territory | Germany |
City | Göttingen |
Period | 24/8/12 → 24/8/16 |
Bibliographical note
Publisher Copyright:© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science