Simple and flexible detection of contiguous repeats using a suffix tree, Theor

Abstract. We study the problem of detecting all occurrences of (prim-itive) tandem repeats and tandem arrays in a string. We rst give a simple time- and space- optimal algorithm to nd all tandem repeats, and then modify it to become a time and space-optimal algorithm for nding only the primitive tandem repeats. Both of these algorithms are then extended to handle tandem arrays. The contribution of this paper is both pedagogical and practical, giving simple algorithms and imple-mentations based on a sux tree, using only standard tree traversal techniques.