Research Online

Logo

Goldsmiths - University of London

Computing maximal-exponent factors in an overlap-free word

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

[img]
Preview
Text
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:

Article

Identification Number (DOI):

https://doi.org/10.1016/j.jcss.2015.11.007

Keywords:

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

Departments, Centres and Research Units:

Computing

Dates:

DateEvent
28 July 2014Published

Item ID:

22721

Date Deposited:

09 Jan 2018 11:45

Last Modified:

11 Jul 2018 13:07

Peer Reviewed:

Yes, this version has been peer-reviewed.

URI:

http://research.gold.ac.uk/id/eprint/22721

View statistics for this item...

Edit Record Edit Record (login required)