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

Пусть даны конечное множество ''строк шаблона'' <math>\mathcal{P} = \{P^1, P^2, ..., Pk \}</math> и ''текстовая строка'' <math>T = t_1 t_2 ... t_n</math>, где <math>T</math> и <math>P^i</math> представляют собой последовательности над алфавитом <math>\Sigma</math> размера <math>\sigma</math>. Задача ''сравнения нескольких строк'' (multiple string matching, MSM) заключается в нахождении одной или, в общем случае, всех текстовых позиций, начиная с которых <math>P^i</math> входит в <math>T</math>; или, говоря более точно, в вычислении множества <math> \{ j | \exists i, P^i = t_j t_{j + 1} ... t_{j + |P^i| - 1} \} </math> или эквивалентного множества <math> \{ j | \exists i, P^i = t_{j - |P^i| + 1} t_{j - |P^i| + 2} ... t_j \} </math>. Отметим, что при выдаче всех вхождений шаблонов размер выходных данных может стать квадратичным (например, в случае, когда <math>P^i</math> и <math>T</math> берутся из однобуквенного алфавита). Обозначим длину самого короткого шаблона в <math>\mathcal{P}</math> за <math>\ell min</math>. Предполагается, что шаблоны задаются в самом начале, после чего производится поиск их вхождения в нескольких текстах. Данная задача является расширением задачи [[Последовательное точное сравнение строк|точного сравнения строк]].

Первое решение задачи сравнения нескольких строк заключается в применении алгоритма точного сравнения строк для локализации каждого шаблона в <math>\mathcal{P}</math>. Сложность этого алгоритма составляет O(kn) в наихудшем случае. Существуют более эффективные решения, основанные на двух подходах. Первый подход, предложенный Ахо и Корасик [1], представляет собой расширение алгоритма сравнения одной строки с помощью конечного автомата. Второй подход, реализованный Комменц-Уолтер [3], расширяет алгоритм Бойера-Мура на случай нескольких шаблонов.