TY - GEN

T1 - Cartesian Tree Subsequence Matching

AU - Oizumi, Tsubasa

AU - Kai, Takeshi

AU - Mieno, Takuya

AU - Inenaga, Shunsuke

AU - Arimura, Hiroki

N1 - Funding Information:
Funding Takuya Mieno: JSPS KAKENHI Grant Number JP20J11983. Shunsuke Inenaga: JST PRESTO Grant Number JPMJPR1922. Hiroki Arimura: JSPS KAKENHI Grant Number 20H00595, JST CREST Grant MJCR18K3.
Funding Information:
Takuya Mieno: JSPS KAKENHI Grant Number JP20J11983. Shunsuke Inenaga: JST PRESTO Grant Number JPMJPR1922. Hiroki Arimura: JSPS KAKENHI Grant Number 20H00595, JST CREST Grant Number JPMJCR18K3.
Publisher Copyright:
© Tsubasa Oizumi, Takeshi Kai, Takuya Mieno, Shunsuke Inenaga, and Hiroki Arimura; licensed under Creative Commons License CC-BY 4.0

PY - 2022/6/1

Y1 - 2022/6/1

N2 - 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].

AB - 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].

UR - http://www.scopus.com/inward/record.url?scp=85134344701&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85134344701&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.CPM.2022.14

DO - 10.4230/LIPIcs.CPM.2022.14

M3 - Conference contribution

AN - SCOPUS:85134344701

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022

A2 - Bannai, Hideo

A2 - Holub, Jan

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022

Y2 - 27 June 2022 through 29 June 2022

ER -