Linear Time Runs over General Ordered Alphabets

Jonas Ellert, Johannes Fischer

A run in a string is a maximal periodic substring. For example, the string $\text{bananatree}$ contains the runs $\text{anana}=(\text{an}{)}^{3/2}$ and $\texttt{ee} = \texttt…