Computing Runs on a General Alphabet

Abstract

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 working in $\Theta (n\log \sigma )$ time provided $\sigma =n^{\Omega (1)}$, where $\sigma$ is the alphabet size. We conjecture that there exists a linear time RAM algorithm finding all runs.

4 pages, 2 figures

References in corpus (2)

• The "Runs" Theorem
• Lempel-Ziv Factorization May Be Harder Than Computing All Runs