Задачи поиска ближайшей строки и ближайшей подстроки: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Задача нахождения центральной строки, «похожей» на каждую заданну…») |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 8: | Строка 8: | ||
Задача 1 (задача нахождения ближайшей строки) | Задача 1 (задача нахождения ближайшей строки) | ||
Дано: набор строк <math>S = \{ s_1, s_2, ..., s_n \}<math>, каждая из которых имеет длину m. | Дано: набор строк <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 \}<math>, каждая из которых имеет длину m. | Дано: целое число 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. |