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

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