We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
String Indexing for Patterns with Wildcards.
- Authors
Bille, Philip; Gørtz, Inge; Vildhøj, Hjalte; Vind, Søren
- 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. We also show that these indexes can be generalized to allow variable length gaps in the pattern. Our results are obtained using a novel combination of well-known and new techniques, which could be of independent interest.
- Subjects
INDEXING; PATTERN recognition systems; VARIABLE-length codes; TREE graphs; GENERALIZATION; MATHEMATICAL combinations
- Publication
Theory of Computing Systems, 2014, Vol 55, Issue 1, p41
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-013-9498-4