Subsequence matching and LCS under Cartesian-tree equivalence

DOI10.1007/S00224-025-10255-6MaRDI QIDQ7233453zbMATH OpenFDO

Authors Taketo Tsujimoto, Yuki Yonemoto, Hiroki Shibata, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga

Publication date 27 April 2026

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00224-025-10255-6

zbMATH Keywords

Cartesian-treeconditional lower boundlongest common subsequencesubsequence matching

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• A linear time algorithm for consecutive permutation pattern matching
• A longest common subsequence algorithm suitable for similar text strings
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Cartesian tree subsequence matching
• Computing longest common subsequence under Cartesian-tree matching model
• Computing the longest common subsequence of two run-length encoded strings
• Fast algorithms for single and multiple pattern Cartesian tree matching
• Fast linear-space computations of longest common subsequences
• Finding patterns and periods in Cartesian tree matching
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• On Indeterminate Strings Matching.
• On the complexity of k-SAT
• Order-preserving matching
• Pattern matching for permutations
• Pattern Matching in Trees
• Quadratic conditional lower bounds for string problems and dynamic time warping
• The fine-grained complexity of episode matching

This page was built for publication: Subsequence matching and LCS under Cartesian-tree equivalence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7233453)