Pattern matching with don't cares: multiple patterns

Question

Kalai's 2-page SODA paper gives a simple and efficient algorithm for pattern matching with don't cares (wildcards that match one character). In essence, it is as easy as convolution.

But what happens if we are searching for multiple patterns with don't cares? Can we still somehow solve it with e.g. FFT-based techniques?

Answer 1

For the multiple pattern case, it seems that simply scanning for each of the might be the best possible solution, at least unless the strong exponential-time hypothesis fails.

Recall that given sets $S_1, S_2, \dotsc, S_n$ and $T_1, T_2, \dotsc, T_n$ over universe $[m]$, if we could decide if there are $S_i$ and $T_j$ such that $S_i \cup T_j = [m]$ in time $O(n^{2-\varepsilon}\operatorname{poly}(m))$, then SETH fails, i.e. we have a CNF-SAT algorithm with running time $O^*\bigl(2^{(1-\varepsilon/2)n}\bigr)$.

Given sets $S_1, S_2, \dotsc, S_n$ and $T_1, T_2, \dotsc, T_n$, we encode the above problem as multi-pattern matching with don't cares over binary alphabet as follows:

• The text is $$1[T_1]10^{m+2}1[T_2]10^{m+2}\dots0^{m+2}1[T_n]1\,,$$ where $[T_i]$ is the natural encoding of $T_i$ as a binary string.
• We have $n$ patterns of form $1\langle S_i \rangle 1$, where $\langle S_i \rangle$ is a string $y = y_1y_2\dots y_m$ such that $y_j = 1$ if $j \notin S_i$ and $y_j = * $ if $j \in S_i$ (here $*$ is the don't care symbol).

Now it's clear that a pattern $1\langle S_i \rangle 1$ can match the text at an occurrence of $1[T_j]1$, and only when $S_i \cup T_j = [m]$. The total length of patterns and the length of the text are both $O(nm)$, for instance so a near-linear single-pass algorithm for multiple patterns would give substantial improvements over best known CNF-SAT algorithms...

(Note that this does not say anything about algorithms that use lots of time preprocessing the patterns, say, quadratic in the total length of the patterns.)