Cartesian Tree Matching and Indexing

DOI10.4230/LIPIcs.CPM.2019.16OpenAlexW2954936350MaRDI QIDQ5088906

Amihood Amir, Sung Gwan Park, Gad M. Landau, Kun Soo 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)

Related Items (2)

Fast algorithms for single and multiple pattern Cartesian tree matching ⋮ Unnamed Item

Cites Work

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

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