Brodal, Gerth Stølting^{4}; Lyngsø, Rune B.^{3}; Pedersen, Christian N. S.^{3}; Stoye, Jens^{3}

Editor:

Maxime Crochemore, Mike Paterson

Affiliations:

^{1} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{2} Department of Computer Science, Science and Technology, Aarhus University^{3} unknown^{4} Department of Computer Science, Science and Technology, Aarhus University

DOI:

10.1007/3-540-48452-3_11

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.

Type:

Conference paper

Language:

English

Published in:

Combinatorial Pattern Matching: 10th Annual Symposium, Cpm 99 Warwick University, Uk, July 22–24, 1999 Proceedings, 1999, p. 134-149

Main Research Area:

Science/technology

Publication Status:

Published

Series:

Lecture Notes in Computer Science

Review type:

Peer Review

Conference:

10th Annual Symposium on Combinatorial Pattern Matching. CPM 99, 1999