Generalized pattern matching and periodicity under substring consistent equivalence relations

DOI10.1016/J.TCS.2016.02.017MaRDI QIDQ507402zbMATH OpenOpenAlexFDO

Authors Yoshiaki Matsuoka, Takahiro Aoki, Shunsuke Inenaga, Hideo Bannai, 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

generalized periodicity lemmaorder-preserving pattern matchingparameterized pattern matchingstring matching algorithm

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• scientific article; zbMATH DE number 7650903
• Generalized dictionary matching under substring consistent equivalence relations
• On matching generalised repetitive patterns
• String matching under a general matching relation
• Subsequence versus substring constraints in sequence pattern languages
• scientific article; zbMATH DE number 4126695
• On string pattern matching: A quantitative analysis and a proposal
• Pattern spectra, substring enumeration, and automatic sequences
• Matching patterns in strings subject to multi-linear transformations

Cites work

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

Cited in

(18)

• On matching generalised repetitive patterns
• Permuted pattern matching algorithms on multi-track strings
• Position heaps for Cartesian-tree matching on strings and tries
• Finding patterns and periods in Cartesian tree matching
• String periods in the order-preserving model
• Parallel duel-and-sweep algorithm for the order-preserving pattern matching
• String Periods in the Order-Preserving Model
• String Covering: A Survey
• Simon's congruence pattern matching
• Computing Covers Under Substring Consistent Equivalence Relations
• Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm
• Breaking a barrier in constructing compact indexes for parameterized pattern matching
• Computing maximal palindromes in non-standard matching models
• Computing maximal palindromes in non-standard matching models
• The ceBWT index: an index for circular Cartesian tree matching on multiple texts
• Extending the Burrows-Wheeler transform for Cartesian tree matching and constructing it
• Fast computation of k-runs, parameterized squares, and other generalised squares
• Generalized dictionary matching under substring consistent equivalence relations

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

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