Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433740 | Theoretical Computer Science | 2016 | 4 Pages |
Abstract
We study the problem of indexing a text T[1…n]T[1…n] such that whenever a pattern P[1…p]P[1…p] and an interval [α,β][α,β] come as a query, we can report all pairs (i,j)(i,j) of consecutive occurrences of P in T with α≤j−i≤βα≤j−i≤β. We present an O(nlogn)O(nlogn) space data structure with optimal O(p+k)O(p+k) query time, where k is the output size.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gonzalo Navarro, Sharma V. Thankachan,