Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints

Gonzalo Navarro and Sharma V. Thankachan

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