Optimality of some algorithms to detect quasiperiodicities

DOI10.1016/j.tcs.2010.04.039zbMath1196.68178OpenAlexW2028897973MaRDI QIDQ986546

Gwenaël Richomme, Richard Groult

Publication date: 11 August 2010

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

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

zbMATH Keywords

quasiperiodicityFibonacci wordsrepetitions in words

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Related Items

Crochemore's partitioning on weighted strings and applications, Computing regularities in strings: a survey

Cites Work

• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• Quasiperiodic Sturmian words and morphisms
• An optimal algorithm for computing the repetitions in a word
• An on-line string superprimitivity test
• How many squares can a string contain?
• The exact number of squares in Fibonacci words
• Testing string superprimitivity in parallel
• An optimal algorithm to compute all the covers of a string
• A characterization of the squares in a Fibonacci string
• Quasiperiodic and Lyndon episturmian words
• On extremal properties of the Fibonacci word
• Algorithms on Strings
• Computing the cover array in linear time
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item