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(nlog23 n) time and linear space. Our algorithm outperforms all known solutions working in Θ(nlog σ) time provided σ=nΩ(1), where σ is the alphabet size. We conjecture that there exists a linear time RAM algorithm finding all runs. © 2015 Elsevier B.V.