Fast algorithms for single and multiple pattern Cartesian tree matching

DOI10.1016/J.TCS.2020.10.009zbMath1464.68447OpenAlexW3092894821MaRDI QIDQ2215968

Simone Faro, Siwoo Song, Geonmo Gu, Cheol Ryu, Thierry Lecroq, Kun Soo Park

Publication date: 15 December 2020

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

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

zbMATH Keywords

fingerprinting methodsCartesian tree matchingglobal-parent representationprefix-child representationprefix-parent representation

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (2)

Position heaps for Cartesian-tree matching on strings and tries ⋮ Approximate Cartesian tree matching: an approach using swaps

Cites Work

• Unnamed Item
• Unnamed Item
• A linear time algorithm for consecutive permutation pattern matching
• A fast algorithm for order-preserving pattern matching
• A filtration method for order-preserving matching
• Improving practical exact string matching
• Alphabet dependence in parameterized matching
• Overlap matching.
• Fast practical multi-pattern matching
• Encoding nearest larger values
• Approximate swapped matching.
• The order-preserving pattern matching problem in practice
• On representations of ternary order relations in numeric strings
• Order-preserving matching
• Fast Multiple Order-Preserving Matching Algorithms
• ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
• A fast string searching algorithm
• Efficient randomized pattern-matching algorithms
• A unifying look at data structures
• Efficient string matching
• Fast Pattern Matching in Strings
• Pattern Matching with Swaps
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• Cartesian Tree Matching and Indexing
• A theory of parameterized pattern matching

This page was built for publication: Fast algorithms for single and multiple pattern Cartesian tree matching