Cartesian Tree Matching and Indexing

DOI10.4230/LIPICS.CPM.2019.16MaRDI QIDQ5088906zbMATH OpenOpenAlexFDO

Authors Sung Gwan Park, Amihood Amir, Gad M. Landau, Kunsoo Park

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1905.08974

zbMATH Keywords

pattern matchingindexingparent-distance representationcartesian tree matching

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Fast algorithms for single and multiple pattern Cartesian tree matching
• Finding patterns and periods in Cartesian tree matching
• Fast multiple pattern Cartesian tree matching
• Fast Cartesian tree matching
• Approximate Cartesian tree matching: an approach using swaps

Cites work

• A Generalization of the Suffix Tree to Square Matrices, with Applications
• A Space-Economical Suffix Tree Construction Algorithm
• A linear time algorithm for consecutive permutation pattern matching
• A theory of parameterized pattern matching
• Algorithms for jumbled pattern matching in strings
• Algorithms – ESA 2004
• Alphabet dependence in parameterized matching
• Approximate swapped matching.
• Efficient string matching
• Fast Pattern Matching in Strings
• Faster suffix tree construction with missing suffix links
• On Cartesian trees and range minimum queries
• On approximate jumbled pattern matching in strings
• On representations of ternary order relations in numeric strings
• On-line construction of parameterized suffix trees for large alphabets
• On-line construction of two-dimensional suffix trees in \(O(n^{2} \log n)\) time
• Order-preserving indexing
• Order-preserving matching
• Overlap matching.
• Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance
• Parameterized matching with mismatches
• Pattern Matching with Swaps
• String Periods in the Order-Preserving Model

Cited in

(5)

• Fast algorithms for single and multiple pattern Cartesian tree matching
• TREE-BASED 2D INDEXING
• scientific article; zbMATH DE number 7559174 (Why is no real title available?)
• Approximate Cartesian tree matching: an approach using swaps
• Fast Cartesian tree matching

This page was built for publication: Cartesian Tree Matching and Indexing

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