String Indexing for Patterns With Wildcards

Philip Bille, Inge Li Gørtz, Hjalte Wedel Vildhøj, Søren Juhl Vind

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

    220 Downloads (Pure)


    We consider the problem of indexing a string t of length n to report the occurrences of a query pattern p containing m characters and j wildcards. Let occ be the number of occurrences of p in t, and σ the size of the alphabet. We obtain the following results. - A linear space index with query time O(m + σj log log n + occ). This significantly improves the previously best known linear space index by Lam et al. [ISAAC 2007], which requires query time Θ(jn) in the worst case. - An index with query time O(m + j + occ) using space O(σk2 n log k log n), where k is the maximum number of wildcards allowed in the pattern. This is the first non-trivial bound with this query time. - A time-space trade-off, generalizing the index by Cole et al. [STOC 2004]. Our results are obtained using a novel combination of well-known and new techniques, which could be of independent interest.
    Original languageEnglish
    Title of host publicationAlgorithm Theory – SWAT 2012 : 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings
    EditorsFedor V. Fornin, Petteri Kaski
    Publication date2012
    ISBN (Print)978-3-642-31154-3
    ISBN (Electronic)978-3-642-31155-0
    Publication statusPublished - 2012
    Event13th Scandinavian Symposium and Workshops on Algorithm Theory - University of Helsinki, Helsinki, Finland
    Duration: 4 Jul 20126 Jul 2012


    Conference13th Scandinavian Symposium and Workshops on Algorithm Theory
    LocationUniversity of Helsinki
    SeriesLecture Notes in Computer Science


    Dive into the research topics of 'String Indexing for Patterns With Wildcards'. Together they form a unique fingerprint.

    Cite this