Generalized pattern matching and periodicity under substring consistent equivalence relations

DOI10.1016/j.tcs.2016.02.017zbMath1356.68304OpenAlexW2281066615MaRDI QIDQ507402

Takahiro Aoki, Yoshiaki Matsuoka, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda

Publication date: 6 February 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.02.017

zbMATH Keywords

order-preserving pattern matchingparameterized pattern matchinggeneralized periodicity lemmastring matching algorithm

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (7)

Position heaps for Cartesian-tree matching on strings and tries ⋮ String Periods in the Order-Preserving Model ⋮ String Covering: A Survey ⋮ Finding patterns and periods in Cartesian tree matching ⋮ Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching ⋮ Permuted pattern matching algorithms on multi-track strings ⋮ String periods in the order-preserving model

Cites Work

• Unnamed Item
• Unnamed Item
• Palindrome pattern matching
• A linear time algorithm for consecutive permutation pattern matching
• A fast algorithm for order-preserving pattern matching
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Periodicity and repetitions in parameterized strings
• Fine and Wilf's theorem for three periods and a generalization of Sturmian words
• Alphabet dependence in parameterized matching
• Parameterized pattern matching: Algorithms and applications
• Order-preserving matching
• On a paper by Castelli, Mignosi, Restivo
• Fast Pattern Matching in Strings
• Uniqueness Theorems for Periodic Functions

This page was built for publication: Generalized pattern matching and periodicity under substring consistent equivalence relations