Computing maximal-exponent factors in an overlap-free word

Abstract : The exponent of a word is the quotient of its length over its smallest period. The exponent and the period of a word can be computed in time proportional to the word length. We design an algorithm to compute the maximal exponent of all factors of an overlap-free word. Our algorithm runs in linear-time on a fixed-size alphabet, while a naive solution of the question would run in cubic time. The solution for non overlap-free words derives from algorithms to compute all maximal repetitions, also called runs, occurring in the word. We also show there is a linear number of occurrences of maximal-exponent factors in an overlap-free word. Their maximal number lies between 0.66n and 2.25n in a word of length n. The algorithm can additionally locate all of them in linear time.
Document type :
Journal articles
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01806284
Contributor : Maxime Crochemore <>
Submitted on : Friday, June 1, 2018 - 6:36:57 PM
Last modification on : Wednesday, June 6, 2018 - 10:21:27 AM
Long-term archiving on : Sunday, September 2, 2018 - 3:46:37 PM

File

maxexp.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01806284, version 1

Collections

Citation

Golnaz Badkobeh, Maxime Crochemore. Computing maximal-exponent factors in an overlap-free word . Journal of Computer and System Sciences, Elsevier, 2016. ⟨hal-01806284⟩

Share

Metrics

Record views

28

Files downloads

88