Approximate Cartesian tree matching with one difference

DOI10.1016/J.TCS.2026.116026MaRDI QIDQ7266663zbMATH OpenFDO

Authors Bastien Auvray, Julien David, Samah Ghazawi, Richard Groult, Gad M. Landau, Thierry Lecroq

Publication date 15 June 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.116026

zbMATH Keywords

approximate pattern matchingCartesian tree matchingdeletioninsertionmismatchswaptransposition

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A linear time algorithm for consecutive permutation pattern matching
• A unifying look at data structures
• Approximate Cartesian tree matching: an approach using swaps
• Approximate Cartesian tree pattern matching
• Bioinformatics algorithms. Sequence analysis, genome rearrangements, and phylogenetic reconstruction
• Cartesian and Lyndon trees
• Cartesian Tree Matching and Indexing
• Cartesian tree subsequence matching
• Computing Covers Under Substring Consistent Equivalence Relations
• Computing longest common subsequence under Cartesian-tree matching model
• Computing maximal palindromes in non-standard matching models
• Efficient string matching
• Fast algorithms for single and multiple pattern Cartesian tree matching
• Fast Pattern Matching in Strings
• Finding patterns and periods in Cartesian tree matching
• On Cartesian trees and range minimum queries
• Order-preserving matching
• Pattern matching with swaps
• Position heaps for Cartesian-tree matching on strings and tries
• Random generation of source vectors with a fixed preponderant property
• The exact online string matching problem: a review of the most recent results
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE

This page was built for publication: Approximate Cartesian tree matching with one difference

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