A fast algorithm for order-preserving pattern matching

DOI10.1016/J.IPL.2014.10.018MaRDI QIDQ477704zbMATHOpenAlexFDO

Authors Sukhyeun Cho, Joong Chae Na, J. S. Sim, Kunsoo 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)

Recommendations

• Fast order-preserving pattern matching
• Fast multiple order-preserving matching algorithms
• Efficient algorithms for the order preserving pattern matching problem
• The order-preserving pattern matching problem in practice
• Duel and sweep algorithm for order-preserving pattern matching

Cites work

• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• A fast string searching algorithm
• A linear time algorithm for consecutive permutation pattern matching
• A simple fast hybrid pattern-matching algorithm
• Fast order-preserving pattern matching
• Introduction to algorithms.
• Linear-Time Ranking of Permutations
• Order-preserving matching

Cited in

(27)

• Order-preserving pattern matching with \(k\) mismatches
• Fast algorithms for single and multiple pattern Cartesian tree matching
• A simple fast hybrid pattern-matching algorithm
• Parallel duel-and-sweep algorithm for the order-preserving pattern matching
• Duel and sweep algorithm for order-preserving pattern matching
• An \(O(n^2\log m)\)-time algorithm for the boxed-mesh permutation pattern matching problem
• scientific article; zbMATH DE number 7559174 (Why is no real title available?)
• Improved algorithms for the boxed-mesh permutation pattern matching problem
• Efficient algorithms for the order preserving pattern matching problem
• Order preserving pattern matching on trees and DAGs
• String Periods in the Order-Preserving Model
• A filtration method for order-preserving matching
• Fast Cartesian tree matching
• Longest common subsequence in at least \(k\) length order-isomorphic substrings
• The order-preserving pattern matching problem in practice
• Order-preserving pattern matching with scaling
• Fast multiple order-preserving matching algorithms
• Order-preserving pattern matching indeterminate strings
• Order-preserving pattern matching indeterminate strings
• Generalized pattern matching and periodicity under substring consistent equivalence relations
• Order-preserving indexing
• Order-preserving pattern matching with \(k\) mismatches
• Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm
• An encoding for order-preserving matching
• Position heaps for Cartesian-tree matching on strings and tries
• Fast order-preserving pattern matching
• String periods in the order-preserving model

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477704)