Dmitry Kosolobov

Computing Runs on a General Alphabet

2015 · arXiv (Cornell University)

We describe a RAM algorithm computing all runs (maximal repetitions) of a given string of length $n$ over a general ordered alphabet in $O(n\log^{\frac{2}3} n)$ time and linear space. Our algorithm outperforms all known solutions …