Computing maximal-exponent factors in an overlap-free word

DOI10.1016/j.jcss.2015.11.007zbMath1333.68303OpenAlexW2185072808WikidataQ61677825 ScholiaQ61677825MaRDI QIDQ899581

Golnaz Badkobeh, Maxime Crochemore

Publication date: 30 December 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://research.gold.ac.uk/id/eprint/22721/1/MaxExpFac.pdf

zbMATH Keywords

periodicityautomatonreturn wordword exponentmaximal repetitionsoverlap-free word

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Algorithms on strings (68W32)

Related Items

Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets, Efficient computation of maximal anti-exponent in palindrome-free strings, Counting maximal-exponent factors in words

Cites Work

• The ``runs conjecture
• Last cases of Dejean's conjecture
• Maximal repetitions in strings
• On maximal repetitions of arbitrary exponent
• Covering a string
• Computing longest previous non-overlapping factors
• The number of runs in a string
• The subtree max gap problem with application to parallel string covering
• Sur un théorème de Thue
• Finite repetition threshold for large alphabets
• Efficient Seeds Computation Revisited
• A proof of Dejean’s conjecture
• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Algorithms on Strings
• A characterization of Sturmian words by return words
• Unnamed Item
• Unnamed Item
• Unnamed Item