Cartesian Tree Subsequence Matching

Tsubasa Oizumi, Takeshi Kai, Takuya Mieno, Shunsuke Inenaga, Hiroki Arimura

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Park et al. [TCS 2020] observed that the similarity between two (numerical) strings can be captured by the Cartesian trees: The Cartesian tree of a string is a binary tree recursively constructed by picking up the smallest value of the string as the root of the tree. Two strings of equal length are said to Cartesian-tree match if their Cartesian trees are isomorphic. Park et al. [TCS 2020] introduced the following Cartesian tree substring matching (CTMStr) problem: Given a text string T of length n and a pattern string of length m, find every consecutive substring S = T[i..j] of a text string T such that S and P Cartesian-tree match. They showed how to solve this problem in Õ(n+m) time. In this paper, we introduce the Cartesian tree subsequence matching (CTMSeq) problem, that asks to find every minimal substring S = T[i..j] of T such that S contains a subsequence S which Cartesian-tree matches P. We prove that the CTMSeq problem can be solved efficiently, in O(mnp(n)) time, where p(n) denotes the update/query time for dynamic predecessor queries. By using a suitable dynamic predecessor data structure, we obtain O(mnlog log n)-time and O(nlog m)-space solution for CTMSeq. This contrasts CTMSeq with closely related order-preserving subsequence matching (OPMSeq) which was shown to be NP-hard by Bose et al. [IPL 1998].

Original languageEnglish
Title of host publication33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022
EditorsHideo Bannai, Jan Holub
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772341
Publication statusPublished - Jun 1 2022
Event33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022 - Prague, Czech Republic
Duration: Jun 27 2022Jun 29 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022
Country/TerritoryCzech Republic

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Cartesian Tree Subsequence Matching'. Together they form a unique fingerprint.

Cite this