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

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

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

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

Пусть даны конечное множество строк шаблона [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] входит в [math]\displaystyle{ T }[/math]; или, говоря более точно, в вычислении множества [math]\displaystyle{ \{ j | \exists i, P^i = t_j t_{j + 1} ... t_{j + |P^i| - 1} \} }[/math], или эквивалентного множества [math]\displaystyle{ \{ j | \exists i, P^i = t_{j - |P^i| + 1} t_{j - |P^i| + 2} ... t_j \} }[/math]. Отметим, что в случае выдачи всех вхождений шаблонов размер выходных данных может стать квадратичным (например, в случае, когда [math]\displaystyle{ P^i }[/math] и [math]\displaystyle{ T }[/math] берутся из однобуквенного алфавита). Обозначим длину самого короткого шаблона в [math]\displaystyle{ \mathcal{P} }[/math] за [math]\displaystyle{ \ell min }[/math]. Предполагается, что шаблоны задаются в самом начале, после чего производится поиск их вхождения в нескольких текстах. Данная задача является расширением задачи точного сравнения строк.

Рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что шаблон и текст генерируются случайным образом посредством равномерного и независимого выбора из [math]\displaystyle{ \Sigma }[/math]. Для простоты и практичности будем далее полагать [math]\displaystyle{ |P^i| = o(n), 1 \le i \le k }[/math].