Simple and efficient methods to find tandem repeats

repeats and tandem arrays in a string. We first give a simple time- and
space-optimal algorithm to find all tandem repeats, and then modify it to
become a time and space-optimal algorithm for finding only the primitive
tandem repeats.
Both of these algorithms are then extended to handle tandem arrays. The
contribution of this work is both pedagogical and practical, giving simple
algorithms and implementations based on a suffix tree, using only standard
tree traversal techniques.

The above algorithms run in worst-case time O(n log n + z) where z is the
size of the output. In the talk I will also sketch more recent developments
which lead to new, truly linear time algorithms to find and represent all
tandem repeats in a string.