Finding patterns and periods in Cartesian tree matching

DOI10.1016/j.tcs.2020.09.014zbMath1454.68208OpenAlexW3086001569MaRDI QIDQ2207506

Sung Gwan Park, Magsarjav Bataa, Gad M. Landau, Amihood Amir, Kun Soo Park

Publication date: 22 October 2020

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.09.014

zbMATH Keywords

pattern matchingperiodsindexingCartesian tree matchingparent-distance representation

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (1)

Position heaps for Cartesian-tree matching on strings and tries

Cites Work

• Unnamed Item
• Unnamed Item
• Order-preserving indexing
• Fast algorithms for abelian periods in words and greatest common divisor queries
• A linear time algorithm for consecutive permutation pattern matching
• Generalized pattern matching and periodicity under substring consistent equivalence relations
• 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 suffix trees
• A note on efficient computation of all abelian periods in a string
• 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
• Prefix Table Construction and Conversion
• ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
• Faster suffix tree construction with missing suffix links
• String Periods in the Order-Preserving Model
• A unifying look at data structures
• 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
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• A Generalization of the Suffix Tree to Square Matrices, with Applications
• A theory of parameterized pattern matching
• A New Model to Solve the Swap Matching Problem and Efficient Algorithms for Short Patterns
• Algorithms – ESA 2004
• Simple and flexible detection of contiguous repeats using a suffix tree

This page was built for publication: Finding patterns and periods in Cartesian tree matching