Subsequence Matching and LCS under Cartesian-Tree Equivalence

Taketo Tsujimoto, Yuki Yonemoto, Hiroki Shibata +3

Two strings of the same length are said to Cartesian-tree match (CT-match) if their Cartesian-trees are isomorphic [Park et al., TCS 2020]. Cartesian-tree matching is a natural mod…