Fast and Practical Algorithms for Computing All the Runs in a String

A repetition in a string x is a substring $${ \bf{w}} = {\it \bf{u}}^e$$ of x, maximum e ≥ 2, where u is not itself a repetition in w. A run in x is a substring $${\it \bf{w}} = {\it \bf{u}}^e{\it \bf{u^{*}}}$$ of “maximal periodicity”, where $${\it \bf{u}}^e$$ is a repetition and u* a maximum-length possibly empty proper prefix of u. A run may encode as many as $$|{\it \bf{u}}|$$ repetitions. The maximum number of repetitions in any string …