Artículo de revista
Reporting consecutive substring occurrences under bounded gap constraints
Fecha
2016Registro en:
Theoretical Computer Science 638 (2016) 108–111
10.1016/j.tcs.2016.02.005
Autor
Navarro, Gonzalo
Thankachan, Sharma V.
Institución
Resumen
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.