La coincidencia de patrones con no le importa: múltiples patrones

El documento SODA de 2 páginas de Kalai ofrece un algoritmo simple y eficiente para la coincidencia de patrones con no importa (comodines que coinciden con un carácter). En esencia, es tan fácil como la convolución.

Pero, ¿qué sucede si estamos buscando patrones múltiples que no le importan? ¿Podemos resolverlo de alguna manera con, por ejemplo, técnicas basadas en FFT?

Para el caso de patrones múltiples, parece que simplemente escanear cada una de ellas podría ser la mejor solución posible, al menos a menos que falle la fuerte hipótesis del tiempo exponencial.

$S_1, S_2, \dotsc, S_n$$T_1, T_2, \dotsc, T_n$$[m]$$S_i$$T_j$$S_i \cup T_j = [m]$$O(n^{2-\varepsilon}\operatorname{poly}(m))$$O^*\bigl(2^{(1-\varepsilon/2)n}\bigr)$

$S_1, S_2, \dotsc, S_n$$T_1, T_2, \dotsc, T_n$

• $$1[T_1]10^{m+2}1[T_2]10^{m+2}\dots0^{m+2}1[T_n]1\,,$$ $[T_i]$$T_i$
• $n$$1\langle S_i \rangle 1$$\langle S_i \rangle$$y = y_1y_2\dots y_m$$y_j = 1$$j \notin S_i$$y_j = *$$j \in S_i$$*$

$1\langle S_i \rangle 1$$1[T_j]1$$S_i \cup T_j = [m]$$O(nm)$

(Tenga en cuenta que esto no dice nada acerca de los algoritmos que usan mucho tiempo preprocesando los patrones, digamos, cuadráticos en la longitud total de los patrones).