Computing Longest Common Subsequence under Cartesian-Tree Matching Model
<|reference_start|>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^6)$ time and $O(n^4)$ space for general ordered alphabets. We then show that the problem has a faster solution in the binary case, by presenting an $O(n^2 / \log n)$-time and space algorithm.<|reference_end|>
@article{tsujimoto2024computing,
    title={Computing Longest Common Subsequence under Cartesian-Tree Matching Model},
    author={Taketo Tsujimoto, Hiroki Shibata, Takuya Mieno, Yuto Nakashima,
  Shunsuke Inenaga},
    journal={arXiv preprint arXiv:2402.19146},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.19146},
    primaryClass={cs.DS}
}