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
time, where k is the output size.