Combinatorics on words began more than a century ago with a demonstration that an infinitely long string with
norepetitions could be constructed on an alphabet of only three letters. Computing allthe repetitions (such as ⋯ TTT⋯ or ⋯ CGACGA⋯ ) in a given string x nis one of the oldest and most important problems of computational stringology, requiring Θ( n)-time computation of all the maximal periodicitiesor runsin x suffix array, the longest common prefix arrayand the Lempel–Ziv factorization, need to be computed in a preprocessing phase. Furthermore, all of this effort is required despite the fact that the expected number of runs in a string is generally a small fraction of the string length. In this paper, I explore the possibility that repetitions (perhaps also other regularities in strings) can be computed in a manner commensurate with the size of the output.