4446
правок
Задачи поиска ближайшей строки и ближайшей подстроки: различия между версиями
Материал из WEGA
Задачи поиска ближайшей строки и ближайшей подстроки (посмотреть исходный код)
Версия от 23:28, 26 октября 2019
, 26 октября 2019нет описания правки
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 8: | Строка 8: | ||
Задача 1 (задача нахождения ближайшей строки) | Задача 1 (задача нахождения ближайшей строки) | ||
Дано: набор строк <math>S = \{ s_1, s_2, ..., s_n \}< | Дано: набор строк <math>S = \{ s_1, s_2, ..., s_n \}</math>, каждая из которых имеет длину m. | ||
Требуется: найти минимальное значение d и строки длины m, находящиеся в пределах расстояния Хэмминга d от каждой строки <math>s_i \in S</math>. | Требуется: найти минимальное значение d и строки длины m, находящиеся в пределах расстояния Хэмминга d от каждой строки <math>s_i \in S</math>. | ||
| Строка 18: | Строка 18: | ||
Задача 2 (задача нахождения ближайшей подстроки) | Задача 2 (задача нахождения ближайшей подстроки) | ||
Дано: целое число L и набор строк <math>S = \{ s_1, s_2, ..., s_n \}< | Дано: целое число L и набор строк <math>S = \{ s_1, s_2, ..., s_n \}</math>, каждая из которых имеет длину m. | ||
Требуется: найти минимальное значение d и строки длины L, находящиеся в пределах расстояния Хэмминга d от имеющей длину L подстроки <math>t_i</math> строки <math>s_i</math> для i = 1, 2, ..., n. | Требуется: найти минимальное значение d и строки длины L, находящиеся в пределах расстояния Хэмминга d от имеющей длину L подстроки <math>t_i</math> строки <math>s_i</math> для i = 1, 2, ..., n. | ||
