On maximal repeats in strings
We clarify in this note the relationship between the maximal repeats in a string p and the compact suffix automaton CSA(p) built on p. It appears that the maximal repeats are the longest strings reaching each internal state of the CSA(p). This result permits to derive the maximal and the average number of maximal repeats (under a model of independence and equiprobability of the characters of p) from earlier studies on the size of CSA(p). It also permits to get a simpler enumeration algorithm of all the maximal repeats in p, using less memory space. (C) 2001 Elsevier Science B.V. All rights reserved.
maximal repeats compact suffix automaton information processing data structures