Последовательное точное сравнение строк: различия между версиями

Алгоритм сканирует символы в окне справа налево, начиная с самого правого символа. В случае несовпадения (либо полного совпадения с шаблоном) он использует две предварительно вычисляемые функции для сдвига шаблона вправо. Эти две функции сдвига носят название ''сдвига плохого символа'' и ''сдвига хорошего суффикса''. Они основаны на следующих наблюдениях. Предположим, что несовпадение обнаруживается между символом <math>p_i = a</math> шаблона и символом <math>t_{i + j} = b</math> текста после попытки в позиции j. Тогда <math>p_{i + 1} ... p_m = t_{i + j + 1} ... t_{j + m} = u</math> и <math>p_i \ne t_{i + j}</math>. Сдвиг хорошего суффикса заключается в выравнивании сегмента <math>t_{i + j + 1} ... t_{j + m}</math> с его самым правым вхождением в P, предшествующим символу, отличному от <math>p_i</math>. Еще один вариант, называемый ''сдвигом лучшего суффикса'', заключается в выравнивании сегмента <math>t_{i + j} ... t_{j + m}</math> с его самым правым вхождением в P. Вычисление обоих вариантов требует O(m) времени и памяти, независимо от размера алфавита. Если такого сегмента не существует, сдвиг заключается в выравнивании самого длинного суффикса v строки <math>t_{i + j + 1} ... t_{j + m}</math> с совпадающим префиксом x. Сдвиг плохого символа заключается в выравнивании символа текста <math>t_{i + j}</math> с его самым правым вхождением в <math>p_1 ... p_{m - 1}</math>. Если <math>t_{i + j}</math> не встречается в шаблоне и никакое вхождение P в T не перекрывает символ <math>t_{i + j}</math>, тогда левый конец шаблона выравнивается с символом в позиции i + j + 1. В этом случае поиск может быть выполнен за время O(n/m) в наилучшем случае.

'''Теорема 5 (Коул, 1994 [5, 14]). В ходе поиска непериодического шаблона P длины m (такой, что длина самой длинной границы P меньше m/2) в тексте T длины n алгоритм Бойера-Мура производит не более 3n сравнений между буквами P и T.'''

'''Теорема 6 (Крочмор и др., 1994 [4]). Поиск может быть выполнен за оптимальное ожидаемое время O((log m/m) x n) с использованием суффиксного конечного автомата или суффиксного дерева реверсивного шаблона.'''

Вместо индексной структуры может использоваться фактор-оракул, поскольку единственной строкой длины m, принимаемая оракулом строки w длины m, является сама строка w. Это выполняется при помощи алгоритма сопоставления с обращенным оракулом (Backward Oracle Matching, BOM) Аллозена, Крочмора и Раффино [1]. На практике его поведение схоже с поведением алгоритма BDM.

'''Теорема 7 (Галил, Сейферас, 1983 [8]). Поиск может быть выполнен оптимальным образом за время O(n) с использованием константного объема памяти.'''

После первого решения Галила и Сейфераса другие варианты были предложены Крочмором и Перреном [6] и Риттером [6]. Алгоритмы разбивают шаблон на две части; вначале они выполняют поиск правой части шаблона слева направо, а затем, если не обнаружено несовпадений, ищут левую часть. Разбиение может представлять собой идеальную факторизацию [8] или критическую факторизацию [8] либо основываться на лексикографически максимальном суффиксе шаблона [13]. Еще одно решение Крочмора [2] представляет собой вариант KMP [11]: оно на лету вычисляет нижние границы периодов префиксов шаблона и не требует предварительной обработки.