  The observed frequency of the longest proper prefix, the longest proper
suffix, and the longest infix of a word $w$ in a given sequence $x$ can be used
for classifying $w$ as avoided or overabundant. The definitions used for the
expectation and deviation of $w$ in this statistical model were described and
biologically justified by Brendel et al. (J Biomol Struct Dyn 1986). We have
very recently introduced a time-optimal algorithm for computing all avoided
words of a given sequence over an integer alphabet (Algorithms Mol Biol 2017).
In this article, we extend this study by presenting an $\mathcal{O}(n)$-time
and $\mathcal{O}(n)$-space algorithm for computing all overabundant words in a
sequence $x$ of length $n$ over an integer alphabet. Our main result is based
on a new non-trivial combinatorial property of the suffix tree $\mathcal{T}$ of
$x$: the number of distinct factors of $x$ whose longest infix is the label of
an explicit node of $\mathcal{T}$ is no more than $3n-4$. We further show that
the presented algorithm is time-optimal by proving that $\mathcal{O}(n)$ is a
tight upper bound for the number of overabundant words. Finally, we present
experimental results, using both synthetic and real data, which justify the
effectiveness and efficiency of our approach in practical terms.

Data Structures and Algorithms