Для случая множественного шаблона, кажется, что простое сканирование для каждого из них могло бы быть наилучшим возможным решением, по крайней мере, если гипотеза сильного экспоненциального времени не верна.
Напомним, что данные наборы S1,S2, ... ,SN а также T1,T2, ... ,TN над вселенной [ м ], если бы мы могли решить, есть ли Sя а также TJ такой, что Sя∪TJ= [ м ] во время O (N2 - εполи( м ) ), тогда SETH терпит неудачу, то есть у нас есть алгоритм CNF-SAT со временем выполнения О*(2( 1 - ε / 2 ) n),
Данные наборы S1,S2, ... ,SN а также T1,T2, ... ,TN, мы кодируем вышеупомянутую проблему как сопоставление с несколькими шаблонами и не заботимся о двоичном алфавите следующим образом:
Теперь ясно, что шаблон 1 ⟨Sя⟩ 1 может соответствовать тексту при появлении 1 [TJ] 1и только когда Sя∪TJ= [ м ], Общая длина шаблонов и длина текста обаO ( n m )Например, почти линейный однопроходный алгоритм для нескольких шаблонов дал бы существенные улучшения по сравнению с наиболее известными алгоритмами CNF-SAT ...
(Обратите внимание, что это ничего не говорит об алгоритмах, которые используют много времени для предварительной обработки шаблонов, скажем, квадратичных по общей длине шаблонов.)