A linear time algorithm for consecutive permutation pattern matching

DOI10.1016/j.ipl.2013.03.015zbMath1370.68341OpenAlexW1974814405WikidataQ60638482 ScholiaQ60638482MaRDI QIDQ396621

Jakub Radoszewski, T. Kulczyński, Wojciech Rytter, Tomasz Walen, Marcin Kubica

Publication date: 13 August 2014

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

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

zbMATH Keywords

analysis of algorithmspattern matchingKnuth-Morris-Pratt algorithmpermutation pattern matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 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 ⋮ 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 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 ⋮ String periods in the order-preserving model ⋮ 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. ⋮ Fast Order-Preserving Pattern Matching ⋮ Order-preserving pattern matching indeterminate strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding pattern matchings for permutations
• Pattern matching for permutations
• A fast algorithm for permutation pattern matching based on alternating runs
• Patterns in permutations and words.
• Stack sortable permutations
• Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
• Consecutive patterns in permutations
• Generalized permutation patterns and a classification of the Mahonian statistics
• Permutations avoiding consecutive patterns. II
• Generalized permutation patterns -- a short survey
• On Complexity of the Subpattern Problem
• Pattern Matching for 321-Avoiding Permutations
• Jewels of Stringology

This page was built for publication: A linear time algorithm for consecutive permutation pattern matching