String indexing for patterns with wildcards

摘要: We consider the problem of indexing a string t length n to report occurrences query pattern p containing m characters and j wildcards. Let occ be number in t, σ size alphabet. obtain following results. – A linear space index with time O(m+σj loglogn+occ). This significantly improves previously best known by Lam et al. [ISAAC 2007], which requires Θ(jn) worst case. – An O(m+j+occ) using $O(\sigma^{k^2} \log^k\log n)$, where k is maximum wildcards allowed pattern. first non-trivial bound this time. – time-space trade-off, generalizing Cole [STOC 2004]. Our results are obtained novel combination well-known new techniques, could independent interest.