|
Title |
Reporting Consecutive Substring Occurrences under Bounded Gap
Constraints |
|
Authors |
Gonzalo Navarro, Sharma Thankachan |
|
Publication date |
2015 |
|
Abstract |
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. |
|
Pages |
367-373 |
|
Conference name |
Annual Symposium on Combinatorial Pattern Matching |
|
Publisher |
Springer-Verlag (Berlin/Heidelberg, Germany) |
|
Reference URL |
|
