Computing the Maximal-Exponent Repeats of an Overlap-Free String in Linear Time

TY - CHAP

T1 - Computing the Maximal-Exponent Repeats of an Overlap-Free String in Linear Time

AU - Badkobeh, Golnaz

AU - Crochemore, Max

AU - Toopsuwan, Chalita

PY - 2012

Y1 - 2012

N2 - The exponent of a string is the quotient of the strings length over the strings smallest period. The exponent and the period of a string can be computed in time proportional to the strings length. We design an algorithm to compute the maximal exponent of 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 show there is a linear number of maximal-exponent repeats in an overlap-free string. The algorithm can locate all of them in linear time.

AB - The exponent of a string is the quotient of the strings length over the strings smallest period. The exponent and the period of a string can be computed in time proportional to the strings length. We design an algorithm to compute the maximal exponent of 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 show there is a linear number of maximal-exponent repeats in an overlap-free string. The algorithm can locate all of them in linear time.

KW - REPETITIONS

KW - DEJEANS CONJECTURE

KW - RUNS

U2 - 10.1007/978-3-642-34109-0_8

DO - 10.1007/978-3-642-34109-0_8

M3 - Conference paper

SN - 9783642341083

T3 - Lecture Notes in Computer Science

SP - 61

EP - 72

BT - String Processing and Information Retrieval

PB - Springer

ER -