Computing runs on a general alphabet

• We connect the longest common extension (LCE) problem with the runs computation.
• On a general ordered alphabets, all known LCE require O(nlog⁡n)O(nlog⁡n) preprocessing.
• Fast LCE on a general alphabet implies a fast runs computation.
• We construct an algorithm that computes O(n)O(n) LCE queries in O(n(log⁡n)23) time.
• Using the fast LCE, we compute all runs in O(n(log⁡n)23) time.

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⁡σ)Θ(nlog⁡σ) time provided σ=nΩ(1)σ=nΩ(1), where σ is the alphabet size. We conjecture that there exists a linear time RAM algorithm finding all runs.