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

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

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

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

Пусть дано конечное множество строк шаблона P = fP1 ;P2 ; Pkg и текстовая строка T = t1t 2.. tn, где T и Pi представляют собой последовательности над алфавитом S размера a. Задача сравнения нескольких строк (multiple string matching, MSM) заключается в нахождении одной или, в общем случае, всех текстовых позиций, начиная с которых Pi входит в 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.