Order-preserving matching

DOI10.1016/j.tcs.2013.10.006zbMath1282.68187arXiv1302.4064MaRDI 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 matching; order relation; multiple pattern matching; KMP algorithm; Aho-Corasick algorithm; numeric string

Mathematics Subject Classification ID

68R15: Combinatorics on words

68W32: Algorithms on strings

Related Items

Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations, Unnamed Item, Unnamed Item, Order Preserving Pattern Matching on Trees and DAGs, Cartesian Tree Matching and Indexing, An Encoding for Order-Preserving Matching., 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, A fast algorithm for order-preserving pattern matching, Generalized pattern matching and periodicity under substring consistent equivalence relations, A filtration method for order-preserving matching, An \(O(n^2\log m)\)-time algorithm for the boxed-mesh permutation pattern matching problem, Order-preserving pattern matching indeterminate strings, Position heaps for Cartesian-tree matching on strings and tries, 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, The order-preserving pattern matching problem in practice, On representations of ternary order relations in numeric strings, Order-preserving pattern matching with scaling, Efficient Algorithms for the Order Preserving Pattern Matching Problem, Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem, Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings, Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching, String Periods in the Order-Preserving Model

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