Approximate Cartesian Tree Pattern Matching

Sungmin Kim, Yo Sub Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationDevelopments in Language Theory - 28th International Conference, DLT 2024, Proceedings
EditorsJoel D. Day, Florin Manea
PublisherSpringer Science and Business Media Deutschland GmbH
Pages189-202
Number of pages14
ISBN (Print)9783031661587
DOIs
Publication statusPublished - 2024
Event28th International Conference on Developments in Language Theory, DLT 2024 - Göttingen, Germany
Duration: 2024 Aug 122024 Aug 16

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14791 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference28th International Conference on Developments in Language Theory, DLT 2024
Country/TerritoryGermany
CityGöttingen
Period24/8/1224/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

Fingerprint

Dive into the research topics of 'Approximate Cartesian Tree Pattern Matching'. Together they form a unique fingerprint.

Cite this