Approximate Cartesian Tree Pattern Matching

Contribution

A venture down the theory of Cartesian trees from the approximate pattern matching perspective.

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.

Recommended citation:

Sungmin Kim and Yo-Sub Han. “Approximate Cartesian Tree Pattern Matching.” International Conference on Developments in Language Theory (DLT), 2024.