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

Пусть даны конечное множество ''строк шаблона'' <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>\Sigma</math>. Для простоты и практичности будем далее полагать <math>|P^i| = o(n), 1 \le i \le k</math>.