@inproceedings{053faee9e22f467ca192a323f608304c,

title = "String Indexing for Patterns With Wildcards",

abstract = "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.",

author = "Philip Bille and G{\o}rtz, {Inge Li} and Vildh{\o}j, {Hjalte Wedel} and Vind, {S{\o}ren Juhl}",

year = "2012",

doi = "10.1007/978-3-642-31155-0_25",

language = "English",

isbn = "978-3-642-31154-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "283--294",

editor = "Fornin, {Fedor V.} and Petteri Kaski",

booktitle = "Algorithm Theory – SWAT 2012",

note = "13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012 ; Conference date: 04-07-2012 Through 06-07-2012",

}