Сопоставление с шаблоном пофиг: несколько шаблонов

9

Двухстраничная статья Kalai SODA предлагает простой и эффективный алгоритм для сопоставления с шаблоном без разницы (подстановочные знаки, которые соответствуют одному символу). По сути, это так же просто, как свертка.

Но что произойдет, если мы ищем несколько паттернов, не заботясь о них? Можем ли мы еще как-нибудь решить это, например, с помощью методов FFT?

Юкка Суомела
источник

Ответы:

5

Для случая множественного шаблона, кажется, что простое сканирование для каждого из них могло бы быть наилучшим возможным решением, по крайней мере, если гипотеза сильного экспоненциального времени не верна.

Напомним, что данные наборы S1,S2,...,SN а также T1,T2,...,TN над вселенной [м], если бы мы могли решить, есть ли Sя а также TJ такой, что SяTJзнак равно[м] во время О(N2-εполи(м)), тогда SETH терпит неудачу, то есть у нас есть алгоритм CNF-SAT со временем выполнения О*(2(1-ε/2)N),

Данные наборы S1,S2,...,SN а также T1,T2,...,TN, мы кодируем вышеупомянутую проблему как сопоставление с несколькими шаблонами и не заботимся о двоичном алфавите следующим образом:

  • Текст
    1[T1]10м+21[T2]10м+2...0м+21[TN]1,
    где [Tя] это естественная кодировка Tя в виде двоичной строки.
  • У нас есть N шаблоны формы 1Sя1, где Sя это строка Yзнак равноY1Y2...Yм такой, что YJзнак равно1 если JSя а также YJзнак равно* если JSя (Вот * это символ пофиг).

Теперь ясно, что шаблон 1Sя1 может соответствовать тексту при появлении 1[TJ]1и только когда SяTJзнак равно[м], Общая длина шаблонов и длина текста обаО(Nм)Например, почти линейный однопроходный алгоритм для нескольких шаблонов дал бы существенные улучшения по сравнению с наиболее известными алгоритмами CNF-SAT ...

(Обратите внимание, что это ничего не говорит об алгоритмах, которые используют много времени для предварительной обработки шаблонов, скажем, квадратичных по общей длине шаблонов.)

Янне Х. Корхонен
источник