Computing Longest Common Subsequence under Cartesian-Tree Matching Model

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 model that allows for capturing similarities of numerical sequences. Oizumi et al. CPM 2022 showed that subsequence pattern matching under CT-matching model can be solved in polynomial time. This current article follows and extends this line of research: We present the first polynomial-time algorithm that finds the longest common subsequence under CT-matching of two given strings S and T of length n, in O (n⁶) time and O (n⁴) space for general ordered alphabets. We then show that the problem has a faster solution in the binary case, by presenting an O (n² / n) -time and space algorithm.