Cartesian Tree Matching and Indexing

DOI10.4230/LIPICS.CPM.2019.16OpenAlexW2954936350MaRDI QIDQ5088906FDOQ5088906

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

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

zbMATH Keywords

pattern matchingindexingparent-distance representationcartesian tree matching

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• Fast algorithms for single and multiple pattern Cartesian tree matching
• Fast Cartesian tree matching
• Approximate Cartesian tree matching: an approach using swaps
• TREE-BASED 2D INDEXING

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)