Abstract
We revisit various string indexing problems with range reporting
features, namely, position-restricted substring searching, indexing
substrings with gaps, and indexing substrings with intervals. We
obtain the following main results.
– We give efficient reductions for each of the above problems to a new
problem, which we call substring range reporting. Hence, we unify
the previous work by showing that we may restrict our attention to
a single problem rather than studying each of the above problems
individually.
– We show how to solve substring range reporting with optimal query
time and little space. Combined with our reductions this leads to
significantly improved time-space trade-offs for the above problems.
In particular, for each problem we obtain the first solutions with
optimal time query and O(n logO(1) n) space, where n is the length
of the indexed string.
Our bounds for substring range reporting are based on a novel combination
of suffix trees and range reporting data structures. The reductions
are simple and general and may apply to other combinations of string
indexing with range reporting.
Original language | English |
---|---|
Title of host publication | Combinatorial Pattern Matching : 22nd Annual Symposium, CPM 2011 Palermo, Italy, June 27-29, 2011 Proceedings |
Volume | 6661 |
Publisher | Springer |
Publication date | 2011 |
Pages | 299-308 |
ISBN (Print) | 978-3-642-21457-8 |
ISBN (Electronic) | 978-3-642-21458-5 |
DOIs | |
Publication status | Published - 2011 |
Event | 22nd Annual Symposium on Combinatorial Pattern Matching - Palermo, Italy Duration: 27 Jun 2011 → 29 Jun 2011 Conference number: 22 |
Conference
Conference | 22nd Annual Symposium on Combinatorial Pattern Matching |
---|---|
Number | 22 |
Country/Territory | Italy |
City | Palermo |
Period | 27/06/2011 → 29/06/2011 |
Series | Lecture Notes in Computer Science |
---|---|
ISSN | 0302-9743 |