4551
правка
Последовательное точное сравнение строк: различия между версиями
Перейти к навигации
Перейти к поиску
Последовательное точное сравнение строк (посмотреть исходный код)
Версия от 14:51, 22 апреля 2019
, 22 апреля 2019→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Точное сравнение с образцом == Постановка задачи == Пусть да…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть даны строка образца P = | Пусть даны ''строка образца'' <math>P = p_1 p_2 ... p_m</math> и ''текстовая строка'' <math>T = t_1 t_2 ... t_n</math>, представляющие собой последовательности над алфавитом <math>\Sigma</math> размера <math>\sigma</math>. Задача ''точного сравнения строк'' (exact string matching, ESM) заключается в нахождении одной или, в общем случае, всех текстовых позиций, начиная с которых P входит в T; иначе говоря, в вычислении множества <math> \{ j | 1 \le j \le n - m + 1, P = t_j t_{j + 1} ... t_{j + m - 1} \} </math>. Предполагается, что образец задан первым, после чего производится поиск его вхождения в нескольких текстах. | ||
Рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что образец и текст генерируются случайным образом посредством равномерного и независимого выбора из | Рассматриваются сложность в наихудшем и в среднем случаях. Во втором варианте предполагается, что образец и текст генерируются случайным образом посредством равномерного и независимого выбора из <math>\Sigma</math>. Для простоты и практичности будем далее полагать m = o(n). | ||
== Основные результаты == | == Основные результаты == | ||