Substring Range Reporting

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    342 Downloads (Pure)

    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 languageEnglish
    Title of host publicationCombinatorial Pattern Matching : 22nd Annual Symposium, CPM 2011 Palermo, Italy, June 27-29, 2011 Proceedings
    Volume6661
    PublisherSpringer
    Publication date2011
    Pages299-308
    ISBN (Print)978-3-642-21457-8
    ISBN (Electronic)978-3-642-21458-5
    DOIs
    Publication statusPublished - 2011
    EventAnnual Symposium on Combinatorial Pattern Matching - Palermo, Italy
    Duration: 1 Jan 2011 → …
    Conference number: 22

    Conference

    ConferenceAnnual Symposium on Combinatorial Pattern Matching
    Number22
    CityPalermo, Italy
    Period01/01/2011 → …
    SeriesLecture Notes in Computer Science
    ISSN0302-9743

    Cite this

    Bille, P., & Gørtz, I. L. (2011). Substring Range Reporting. In Combinatorial Pattern Matching: 22nd Annual Symposium, CPM 2011 Palermo, Italy, June 27-29, 2011 Proceedings (Vol. 6661, pp. 299-308). Springer. Lecture Notes in Computer Science https://doi.org/10.1007/978-3-642-21458-5_26