# Finding Maximal Pairs with Bounded Gap

In * Proc. 10th Annual Symposium on Combinatorial Pattern Matching*, volume 1645 of * Lecture Notes in Computer Science*, pages 134-149. Springer Verlag, Berlin, 1999.

## 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 *n* we can find all maximal pairs with gap in an
upper and lower bounded interval in time *O*(*n* log *n* + *z*) where *z*
is the number of reported pairs. If the upper bound is removed the
time reduces to *O*(*n* + *z*). 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.

**Copyright notice**
© Springer-Verlag Berlin Heidelberg 1999. All rights reserved.

**Online version**

cpm99.pdf (251 Kb)

**DOI**

10.1007/3-540-48452-3_11

**Links**

**BIBT**_{E}X entry

@incollection{cpm99,
author = "Gerth St{\o}lting Brodal and Rune Bang Lyngs{\o} and Christian N{\o}rgaard Storm Pedersen and Jens Stoye",
booktitle = "Proc. 10th Annual Symposium on Combinatorial Pattern Matching",
doi = "10.1007/3-540-48452-3_11",
isbn = "978-3-540-66278-5",
pages = "134-149",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "Finding Maximal Pairs with Bounded Gap",
volume = "1645",
year = "1999"
}