Computing maximal-exponent factors in an overlap-free word

Tools

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]

Preview

Text
MaxExpFac.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial.
Download (247kB) | Preview

Official URL: https://www.sciencedirect.com/science/article/pii/...

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