2026-07-21T12:30:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16141 2024-03-06T10:56:40Z ddc:004 open_access

Cartesian Tree Subsequence Matching Oizumi, Tsubasa Kai, Takeshi Mieno, Takuya Inenaga, Shunsuke Arimura, Hiroki string algorithms pattern matching Cartesian tree subsequence matching order preserving matching episode matching 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(m n p(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(mn log log n)-time and O(n log 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tsubasa Oizumi and Takeshi Kai and Takuya Mieno and Shunsuke Inenaga and Hiroki Arimura 2022 Is Part Of LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2022.14 urn:nbn:de:0030-drops-161414 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.14 eng https://creativecommons.org/licenses/by/4.0/legalcode