Order-preserving matching

DOI10.1016/j.tcs.2013.10.006zbMath1282.68187arXiv1302.4064OpenAlexW2017575427MaRDI QIDQ2437748

Peter Eades, Rudolf Fleischer, Takeshi Tokuyama, Costas S. Iliopoulos, Simon J. Puglisi, Seok-Hee Hong, Jinil Kim, Kun Soo Park

Publication date: 13 March 2014

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

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

zbMATH Keywords

string matchingorder relationmultiple pattern matchingKMP algorithmAho-Corasick algorithmnumeric string

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items (27)

On representations of ternary order relations in numeric strings ⋮ Order-preserving indexing ⋮ Order-preserving pattern matching with \(k\) mismatches ⋮ A fast algorithm for permutation pattern matching based on alternating runs ⋮ Maximum number of distinct and nonequivalent nonstandard squares in a word ⋮ Position heaps for Cartesian-tree matching on strings and tries ⋮ String Periods in the Order-Preserving Model ⋮ Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem ⋮ A filtration method for order-preserving matching ⋮ Order-preserving pattern matching with scaling ⋮ Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations ⋮ An \(O(n^2\log m)\)-time algorithm for the boxed-mesh permutation pattern matching problem ⋮ Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings ⋮ Finding patterns and periods in Cartesian tree matching ⋮ Fast algorithms for single and multiple pattern Cartesian tree matching ⋮ A framework for designing space-efficient dictionaries for parameterized and order-preserving matching ⋮ A fast algorithm for order-preserving pattern matching ⋮ Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching ⋮ Order Preserving Pattern Matching on Trees and DAGs ⋮ Generalized pattern matching and periodicity under substring consistent equivalence relations ⋮ Unnamed Item ⋮ The order-preserving pattern matching problem in practice ⋮ Cartesian Tree Matching and Indexing ⋮ Efficient Algorithms for the Order Preserving Pattern Matching Problem ⋮ Unnamed Item ⋮ An Encoding for Order-Preserving Matching. ⋮ Order-preserving pattern matching indeterminate strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances
• On special families of morphisms related to \(\delta \)-matching and don't care symbols
• Preserving order in a forest in less than logarithmic time and linear space
• Alphabet dependence in parameterized matching
• Overlap matching.
• Approximate string matching for music analysis
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Efficient 2-dimensional approximate matching of half-rectangular figures
• Approximate matching in the \(L_{\infty }\) metric
• Generalized function matching
• A fast string searching algorithm
• EFFICIENT ALGORITHMS FOR (δ,γ,α) AND (δ, k_Δ, α)-MATCHING
• Algorithms on Extended (δ, γ)-Matching
• Jewels of Stringology
• Pattern Matching with Swaps
• Algorithms For Computing Approximate Repetitions In Musical Sequences
• A theory of parameterized pattern matching
• Function Matching
• Experimental and Efficient Algorithms
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching

This page was built for publication: Order-preserving matching