Finding Maximal Pairs with Bounded Gap

Gerth Stølting Brodal, Rune Bang Lyngsø, Christian Nørgaard Storm Pedersen, and Jens Stoye

In Journal of Discrete Algorithms, Special Issue of Matching Patterns, volume 1(1), pages 77-104, 2000.


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, and 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 with gap zero, our methods is a generalization of finding tandem repeats. The running time of our methods also equals the running time of well known methods for finding tandem repeats.

Online version

jda00.pdf (259 Kb)

BIBTEX entry

  author = "Gerth St{\o}lting Brodal and Rune Bang Lyngs{\o} and Christian N{\o}rgaard Storm Pedersen and Jens Stoye",
  isbn = "190339807X",
  journal = "Journal of Discrete Algorithms, Special Issue of Matching Patterns",
  number = "1",
  pages = "77-104",
  publisher = "Hermes Science Publishing Ltd, Oxford 2000",
  title = "Finding Maximal Pairs with Bounded Gap",
  volume = "1",
  year = "2000"

Other versions