Book chapter · Conference paper
String Indexing for Patterns With Wildcards
Department of Informatics and Mathematical Modeling, Technical University of Denmark1
Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark2
Computer Science and Engineering, Department of Informatics and Mathematical Modeling, Technical University of Denmark3
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.
| Language: | English |
|---|---|
| Publisher: | Springer |
| Year: | 2012 |
| Pages: | 283-294 |
| Proceedings: | 13th Scandinavian Symposium and Workshops on Algorithm Theory |
| Series: | Lecture Notes in Computer Science |
| Journal subtitle: | 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings |
| ISBN: | 3642311547 , 3642311555 , 9783642311543 and 9783642311550 |
| ISSN: | 16113349 and 03029743 |
| Types: | Book chapter and Conference paper |
| DOI: | 10.1007/978-3-642-31155-0_25 |
| ORCIDs: | Bille, Philip and Gørtz, Inge Li |
