@inbook{ac77791decd1436393e09069a32fe52f,

title = "Computing the Maximal-Exponent Repeats of an Overlap-Free String in Linear Time",

abstract = "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.",

keywords = "REPETITIONS, DEJEANS CONJECTURE, RUNS",

author = "Golnaz Badkobeh and Max Crochemore and Chalita Toopsuwan",

year = "2012",

doi = "10.1007/978-3-642-34109-0_8",

language = "English",

isbn = "9783642341083",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "61--72",

booktitle = "String Processing and Information Retrieval",

}