Dopasowywanie wzorów za pomocą nie obchodzi: wiele wzorów

2-stronicowy papier SODA Kalai zapewnia prosty i skuteczny algorytm dopasowywania wzorców bez obojętności (symbole wieloznaczne pasujące do jednej postaci). Zasadniczo jest to tak łatwe jak splot.

Ale co się stanie, jeśli szukamy wielu wzorów z „nie obchodzi”? Czy nadal możemy jakoś rozwiązać to za pomocą np. Technik opartych na FFT?

W przypadku wielokrotnego wzorca wydaje się, że po prostu skanowanie każdego z nich może być najlepszym możliwym rozwiązaniem, przynajmniej jeśli nie powiedzie się silna hipoteza wykładniczego czasu.

Przypomnij sobie, że podane zestawy $S_1, S_2, \dotsc, S_n$ i $T_1, T_2, \dotsc, T_n$ nad wszechświatem $[m]$, gdybyśmy mogli zdecydować, czy są $S_i$ i $T_j$ takie, że $S_i \cup T_j = [m]$ w samą porę $O(n^{2-\varepsilon}\operatorname{poly}(m))$, następnie SETH kończy się niepowodzeniem, tzn. mamy algorytm CNF-SAT z czasem działania $O^*\bigl(2^{(1-\varepsilon/2)n}\bigr)$.

Podane zestawy $S_1, S_2, \dotsc, S_n$ i $T_1, T_2, \dotsc, T_n$, kodujemy powyższy problem jako dopasowanie wielu wzorców za pomocą nie dbaj o binarny alfabet w następujący sposób:

• Tekst jest $$1[T_1]10^{m+2}1[T_2]10^{m+2}\dots0^{m+2}1[T_n]1\,,$$ gdzie $[T_i]$ jest naturalnym kodowaniem $T_i$ jako ciąg binarny.
• Mamy $n$ wzory formy $1\langle S_i \rangle 1$, gdzie $\langle S_i \rangle$ jest ciągiem $y = y_1y_2\dots y_m$ takie, że $y_j = 1$ gdyby $j \notin S_i$ i $y_j = *$ gdyby $j \in S_i$ (tutaj $*$ to symbol „nie obchodzi mnie”).

Teraz jest jasne, że wzór $1\langle S_i \rangle 1$ może dopasować tekst przy wystąpieniu $1[T_j]1$i tylko wtedy, gdy $S_i \cup T_j = [m]$. Całkowita długość wzorów i długość tekstu są równe$O(nm)$, na przykład prawie liniowy algorytm jednoprzebiegowy dla wielu wzorów dałby znaczną poprawę w stosunku do najbardziej znanych algorytmów CNF-SAT ...

(Należy zauważyć, że nie mówi to nic o algorytmach, które wykorzystują dużo czasu na wstępne przetwarzanie wzorców, powiedzmy, kwadratowe w całkowitej długości wzorców).