Computing maximal-exponent factors in an overlap-free word

Badkobeh, Golnaz and Crochemore, Maxime. 2016. Computing maximal-exponent factors in an overlap-free word. Journal of Computer and System Sciences, 82(3), pp. 477-487. ISSN 0022-0000 [Article]

MaxExpFac.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial.

Download (247kB) | Preview

Abstract or Description

The exponent of a string is the quotient of its length over its smallest period. The exponent and the period of a string can be computed in time proportional to the string length. We design an algorithm to compute the maximal exponent of all factors of an overlap-free string. 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 strings derives from algorithms to compute all maximal repetitions, also called runs, occurring in the string.

We also show there is a linear number of occurrences of maximal-exponent factors in an overlap-free string. Their maximal number lies between 0.66n and 2.25n in a string of length n. The algorithm can additionally locate all of them in linear time.

Item Type:


Identification Number (DOI):


Word, string, repetition, power, repeat, periodicity, string exponent, return word, algorithm, automaton.

Departments, Centres and Research Units:



27 August 2014Accepted
2 December 2015Published Online
May 2016Published

Item ID:


Date Deposited:

09 Jan 2018 11:45

Last Modified:

13 Nov 2020 09:32

Peer Reviewed:

Yes, this version has been peer-reviewed.


View statistics for this item...

Edit Record Edit Record (login required)