Abstract:
A pair in a string is the occurrence of the same substring
twice. A pair is maximal if the two occurrences of the substring cannot be
extended to the left and right without making them different. The gap of a
pair is the number of characters between the two occurrences of the
substring. In this paper we present methods for finding all maximal pairs
under various constraints on the gap. In a string of length 
we can find
all maximal pairs with gap in an upper and lower bounded interval in time
where 
is the number of reported pairs. If the upper
bound is removed the time reduces to 
. Since a tandem repeat is a
pair where the gap is zero, our methods can be seen as a generalization of
finding tandem repeats. The running time of our methods equals the running
time of well known methods for finding tandem repeats
we can find
all maximal pairs with gap in an upper and lower bounded interval in time
where is the number of reported pairs. If the upper
bound is removed the time reduces to . Since a tandem repeat is a
pair where the gap is zero, our methods can be seen as a generalization of
finding tandem repeats. The running time of our methods equals the running
time of well known methods for finding tandem repeatsAvailable as PostScript, PDF.