Extracting powers and periods in a word from its runs structure


A breakthrough in the field of text algorithms was the discovery of the fact that the maximal number of runs in a word of length $n$ is $O(n)$ and that they can all be computed in $O(n)$ time. We study some applications of this result. New simpler $O(n)$ time algorithms are presented for classical textual problems: computing all distinct $k$-th word powers for a given $k$, in particular squares for $k=2$, and finding all local periods in a given word of length $n$. Additionally, we present an efficient algorithm for testing primitivity of factors of a word and computing their primitive roots. Applications of runs, despite their importance, are underrepresented in existing literature (approximately one page in the paper of Kolpakov and Kucherov, 1999). In this paper we attempt to fill in this gap. We use Lyndon words and introduce the Lyndon structure of runs as a useful tool when computing powers. In problems related to periods we use some versions of the Manhattan skyline problem.

Theoretical Computer Science 521:29-41
Journal (see conference version)