Задачи поиска ближайшей строки и ближайшей подстроки: различия между версиями
Перейти к навигации
Перейти к поиску
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. | ||
== Основные результаты == | == Основные результаты == |