Последовательное сравнение нескольких строк

Ключевые слова и синонимы

Сравнение со словарем

Постановка задачи

Пусть даны конечное множество строк шаблона [math]\displaystyle{ \mathcal{P} = \{P^1, P^2, ..., Pk \} }[/math] и текстовая строка [math]\displaystyle{ T = t_1 t_2 ... t_n }[/math], где [math]\displaystyle{ T }[/math] и [math]\displaystyle{ P^i }[/math] представляют собой последовательности над алфавитом [math]\displaystyle{ \Sigma }[/math] размера [math]\displaystyle{ \sigma }[/math]. Задача сравнения нескольких строк (multiple string matching, MSM) заключается в нахождении одной или, в общем случае, всех текстовых позиций, начиная с которых [math]\displaystyle{ P^i }[/math] входит в T; или, говоря более точно, в вычислении множества fj j 9i; Pi = tjtj+1 tj,+|j.i|_1g, или эквивалентного множества fj j 9i; Pi = fj_|pi|+i fj_|pi|+2 tjg. Отметим, что в случае выдачи всех вхождений шаблонов размер выходных данных может стать квадратичным (например, в случае, когда Pi и T берутся из однобуквенного алфавита). Обозначим длину самого короткого шаблона в P за imin. Предполагается, что шаблоны задаются в самом начале, после чего производится поиск их вхождения в нескольких текстах. Данная задача является расширением задачи точного сравнения строк.

Рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что шаблон и текст генерируются случайным образом посредством равномерного и независимого выбора из E. Для простоты и практичности будем далее полагать jPi j = o(n), 1 < i < k.