Space-Efficient String Indexing for Wildcard Pattern Matching

In this paper we describe compressed indexes that support pattern matching queries for strings with wildcards. For a constant size alphabet our data structure uses $O(n{\log }^{\epsilon }n)$ bits for any $\epsilon >0$ and reports all $\mathrm{o}\mathrm{c}\mathrm{c}$ occurrences of a wildcard string in $O(m+\sigma^g \cdot\mu(n) + $\mathrm{o}\mathrm{c}\mathrm{c}$)$time,where$\mu(n)=o(\log\log\log n)$,$\sigma$isthealphabetsize,$m$isthenumberofalphabetsymbolsand$g$ is the number of wildcard symbols in the query string. We also present an $O(n)$-bit index with $O((m+{\sigma }^g+\mathrm{o}\mathrm{c}\mathrm{c}){\log }^{\epsilon }n)$ query time and an $O(n(\log \log n{)}^2)$-bit index with $O((m+{\sigma }^g+\mathrm{o}\mathrm{c}\mathrm{c})\log \log n)$ query time. These are the first non-trivial data structures for this problem that need $o(n\log n)$ bits of space.