4551
правка
Последовательное сравнение нескольких строк: различия между версиями
Перейти к навигации
Перейти к поиску
Последовательное сравнение нескольких строк (посмотреть исходный код)
Версия от 14:21, 30 апреля 2019
, 30 апреля 2019→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Сравнение со словарем == Постановка задачи == Пусть дано кон…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть | Пусть даны конечное множество ''строк шаблона'' <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> входит в 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. Предполагается, что шаблоны задаются в самом начале, после чего производится поиск их вхождения в нескольких текстах. Данная задача является расширением задачи точного сравнения строк. | ||