Publication: Research - peer-review › Article in proceedings – Annual report year: 2011
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.
|Title of host publication||Combinatorial Pattern Matching : 22nd Annual Symposium, CPM 2011 Palermo, Italy, June 27-29, 2011 Proceedings|
|State||Published - 2011|
|Conference||Annual Symposium on Combinatorial Pattern Matching|
|Period||01/01/2011 → …|
|Name||Lecture Notes in Computer Science|
|Citations||Web of Science® Times Cited: No match on DOI|
Loading map data...