4446
правок
Задачи поиска ближайшей строки и ближайшей подстроки: различия между версиями
Материал из WEGA
Задачи поиска ближайшей строки и ближайшей подстроки (посмотреть исходный код)
Версия от 13:39, 27 октября 2019
, 27 октября 2019→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 42: | Строка 42: | ||
Формальное определение задачи выглядит следующим образом. Пусть даны множество <math>B = \{ s_1, s_2, ..., s_{n_1} \}</math> из <math>n_1</math> (плохих) строк длиной не менее L и множество <math>G = \{ g_1, g_2, ..., g_{n_2} \}</math> из <math>n_2</math> (хороших) строк, длина которых в точности равна, а также два целых числа <math>d_b</math> и <math>d_g</math> <math>(d_b \le d_g)</math>. Задача выбора различающей подстроки (distinguishing substring selection problem, DSSP) заключается в нахождении строки s, такой, что для каждой строки | Формальное определение задачи выглядит следующим образом. Пусть даны множество <math>B = \{ s_1, s_2, ..., s_{n_1} \}</math> из <math>n_1</math> (плохих) строк длиной не менее L и множество <math>G = \{ g_1, g_2, ..., g_{n_2} \}</math> из <math>n_2</math> (хороших) строк, длина которых в точности равна, а также два целых числа <math>d_b</math> и <math>d_g</math> <math>(d_b \le d_g)</math>. Задача выбора различающей подстроки (distinguishing substring selection problem, DSSP) заключается в нахождении строки s, такой, что для каждой строки <math>s_i \in B</math> существует имеющая длину L подстрока <math>t_i</math> строки <math>s_i</math> с <math>d(s, t_i) \le d_b</math>, и для каждой строки <math>g_i \in G</math> имеет место <math>d(s, g_i) \ge d_g</math>. Здесь d(,) обозначает расстояние Хэмминга между двумя строками. Если все строки в множестве B также имеют длину L, задача называется задачей поиска различающей строки (distinguishing string problem, DSP). | ||
