<p>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.</p>

<p>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)$.</p>

<p>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:</p>

<ul>
<li>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.</li>
<li>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).</li>
</ul>

<p>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 <em>substantial</em> improvements over best known CNF-SAT algorithms...</p>

<p>(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.)</p>

CC BY-SA 3.0
2016-11-04T18:13:41.013Z
2016-11-04T18:13:41.013Z
Janne H. Korhonen
<p><a href="http://dl.acm.org/citation.cfm?id=545381.545468" rel="noreferrer">Kalai's 2-page SODA paper</a> gives a simple and efficient algorithm for pattern matching with <strong>don't cares</strong> (wildcards that match one character). In essence, it is as easy as convolution.</p>

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

<ds.algorithms><reference-request><string-matching>
Pattern matching with don't cares: multiple patterns
Jukka Suomela
# Pattern matching with don't cares: multiple patterns

(Asked by: username_0 on 2016-11-03)

[Kalai's 2-page SODA paper](http://dl.acm.org/citation.cfm?id=545381.545468) 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?

**Tags:** ds.algorithms, reference-request, string-matching

---

## 1 answers

### Answer by username_1 on 2016-11-04. Score: 5 | Accepted answer

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.)


---

