Crochemore's repetitions algorithm revisited -computing runs

Crochemore's repetitions algorithm introduced in 1981 was the first O(n log n) algorithm for computing repetitions. Since then, several linear-time worst- case algorithms for computing runs have been introduced. They all follow a similar strategy: first compute the suffix tree or array, then use the suffix tree or array to com- pute the Lempel-Ziv factorization, then using the Lempel-Ziv factorization compute all the runs. It is conceivable …