  A run in a string is a maximal periodic substring. For example, the string
$\texttt{bananatree}$ contains the runs $\texttt{anana} = (\texttt{an})^{3/2}$
and $\texttt{ee} = \texttt{e}^2$. There are less than $n$ runs in any
length-$n$ string, and computing all runs for a string over a linearly-sortable
alphabet takes $\mathcal{O}(n)$ time (Bannai et al., SODA 2015). Kosolobov
conjectured that there also exists a linear time runs algorithm for general
ordered alphabets (Inf. Process. Lett. 2016). The conjecture was almost proven
by Crochemore et al., who presented an $\mathcal{O}(n\alpha(n))$ time algorithm
(where $\alpha(n)$ is the extremely slowly growing inverse Ackermann function).
We show how to achieve $\mathcal{O}(n)$ time by exploiting combinatorial
properties of the Lyndon array, thus proving Kosolobov's conjecture.
