A fast algorithm for order-preserving pattern matching

DOI10.1016/j.ipl.2014.10.018zbMath1302.68337OpenAlexW2077578233MaRDI QIDQ477704

Jeong Seop Sim, Sukhyeun Cho, Joong Chae Na, Kun Soo Park

Publication date: 9 December 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2014.10.018

zbMATH Keywords

analysis of algorithmsorder-preserving pattern matchingHorspool algorithmKMP algorithmorder-isomorphism

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (17)

Order-preserving indexing ⋮ 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 ⋮ 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 ⋮ Fast algorithms for single and multiple pattern Cartesian tree 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 ⋮ String periods in the order-preserving model ⋮ Unnamed Item ⋮ An Encoding for Order-Preserving Matching. ⋮ Order-preserving pattern matching indeterminate strings

Cites Work

• Unnamed Item
• Unnamed Item
• A linear time algorithm for consecutive permutation pattern matching
• A simple fast hybrid pattern-matching algorithm
• Order-preserving matching
• Fast Order-Preserving Pattern Matching
• A fast string searching algorithm
• Linear-Time Ranking of Permutations

This page was built for publication: A fast algorithm for order-preserving pattern matching