String Periods in the Order-Preserving Model

DOI10.4230/LIPIcs.STACS.2018.38zbMath1487.68260arXiv1801.01404OpenAlexW2971583820MaRDI QIDQ3304137

Arseny M. Shur, Tomasz Kociumaka, Garance Gourdel, Tomasz Walen, Jakub Radoszewski, Wojciech Rytter

Publication date: 5 August 2020

Full work available at URL: https://arxiv.org/abs/1801.01404

zbMATH Keywords

periodefficient algorithmorder-preserving pattern matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Algorithms on strings (68W32)

Related Items (3)

Finding patterns and periods in Cartesian tree matching ⋮ String periods in the order-preserving model ⋮ Cartesian Tree Matching and Indexing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Order-preserving indexing
• Order-preserving pattern matching with \(k\) mismatches
• A note on easy and efficient computation of full abelian periods of a word
• Fast algorithms for abelian periods in words and greatest common divisor queries
• A linear time algorithm for consecutive permutation pattern matching
• A fast algorithm for order-preserving pattern matching
• Algorithms for computing abelian periods of words
• Generalized pattern matching and periodicity under substring consistent equivalence relations
• A filtration method for order-preserving matching
• Graph connectivity, partial words, and a theorem of Fine and Wilf
• Periodicity and repetitions in parameterized strings
• Fine and Wilf's theorem for three periods and a generalization of Sturmian words
• Partial words and a theorem of Fine and Wilf
• Consecutive patterns in permutations
• Fine and Wilf words for any periods
• A note on efficient computation of all abelian periods in a string
• Order-preserving matching
• On a paper by Castelli, Mignosi, Restivo
• Subquadratic-Time Algorithms for Abelian Stringology Problems
• Efficient Algorithms for the Order Preserving Pattern Matching Problem
• Single and Multiple Consecutive Permutation Motif Search
• Periodic Partial Words and Random Bipartite Graphs
• Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries
• Jewels of Stringology
• Partial words and the interaction property of periods
• An Encoding for Order-Preserving Matching.
• Uniqueness Theorems for Periodic Functions
• Abelian periods, partial words, and an extension of a theorem of Fine and Wilf
• Partial words and a theorem of Fine and Wilf revisited

This page was built for publication: String Periods in the Order-Preserving Model