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

Пусть даны ''строка шаблона'' <math>P = p_1 p_2 ... p_m</math> и ''текстовая строка'' <math>T = t_1 t_2 ... t_n</math>, представляющие собой последовательности над алфавитом <math>\Sigma</math> размера <math>\sigma</math>. Задача ''точного сравнения строк'' (exact string matching, ESM) заключается в нахождении одной или, в общем случае, всех текстовых позиций, в которых P входит в T; иначе говоря, в вычислении множества <math> \{ j | 1 \le j \le n - m + 1, P = t_j t_{j + 1} ... t_{j + m - 1} \} </math>. Предполагается, что шаблон задается первым, после чего производится поиск его вхождения в нескольких текстах.

Алгоритм решения задачи ESM полным перебором выполняет проверку вхождения P на каждой позиции j строки T, где <math>1 \le j \le n - m + 1</math>. Ему не требуется этап предварительной обработки. Этот алгоритм требует O(mn) времени и константной дополнительной памяти и в среднем производит O(n) сравнений символов. Его можно сравнить со следующими границами.

'''Теорема 1 (Коул и коллеги, 1995 [3]). Минимальное количество сравнений символов для решения задачи ESM в наихудшем случае оказывается больше или равно n + 9/(4m)(n - m) и может быть сделано меньше или равно n + 8/(3(m + 1))(n - m).'''

Поиск можно осуществить с использованием реализованного детерминированного конечного автомата с поиском потомка по умолчанию <math>\mathcal{D}(P)</math>, распознающего язык <math>\Sigma * P</math>. Размер реализации  составляет O(m) и не зависит от размера алфавита в силу того, что автомат <math>\mathcal{D}(P)</math> имеет m + 1 состояний, m прямых дуг и не более m обратных дуг. Использование конечного автомата для поиска в тексте позволяет получить алгоритм с эффективной задержкой (представляющей собой максимальное время обработки символа текста).

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

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