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