Understanding maximal repetitions in strings

Maxime Crochemore, Lucian Ilie

The cornerstone of any algorithm computing all repetitions in a string of length n in O(n) time is the fact that the number of runs (or maximal repetitions) is O(n). We give a simp…