Optimal Computation of all Repetitions in a Weighted String

A repetition in a string of letters consists of exact concatenations of identical factors of the string. Crochemore’s repetitions algorithm, usually also referred to as Crochemore’s partitioning algorithm, was introduced in 1981, and was the first optimal O(n log n)-time algorithm to compute all repetitions in a string of length n. A weighted string is a string in which a set of letters may occur at each position with respective probabilities of occurrence. In this article, we present a new variant of Crochemore’s partitioning algorithm for weighted strings, which requires optimal time O(n log n), thus improving on the best known O(n2)-time algorithm for computing all repetitions in a weighted string of length n.