Reporting consecutive substring occurrences under bounded gap constraints

Abstract

We study the problem of indexing a text T[1...n] such that whenever a pattern P[1...p] and an interval [alpha, beta] come as a query, we can report all pairs (i, j) of consecutive occurrences of P in T with alpha <= j - i <= beta. We present an O (n logn) space data structure with optimal O (p + k) query time, where k is the output size.