Approximate Cartesian Tree Pattern Matching

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.