Аноним

Нахождение ближайшей подстроки: различия между версиями

Материал из WEGA

Нахождение ближайшей подстроки (посмотреть исходный код)

Версия от 16:26, 1 декабря 2019

123 байта добавлено ,  1 декабря 2019
м
→‎Постановка задачи
(Новая страница: «== Ключевые слова и синонимы == Нахождение приближенной общей подстроки == Постановка зад…»)
 
Строка 8: Строка 8:
Нахождение ближайшей подстроки (CLOSEST SUBSTRING)
Нахождение ближайшей подстроки (CLOSEST SUBSTRING)


Дано: k строк s1, s2, ..., sk над алфавитом S и неотрицательные целые числа d и L.
Дано: k строк <math>s_1, s_2, ..., s_k</math> над алфавитом <math>\Sigma</math> и неотрицательные целые числа d и L.
Вопрос: существует ли строка s длины L, а также существует ли для всех i = 1, ..., k подстрока s0i  строки si длины L, такая, что


Вопрос: существует ли строка s длины L, а также существует ли для всех i = 1, ..., k подстрока <math>s'_i</math> строки <math>s_i</math> длины L, такая, что <math>d_H(s, s'_i) \le d</math>?


Здесь dH(s, s0i) обозначает расстояние Хэмминга между s и si0, т. е. количество позиций, в которых s и si0 различаются. Согласно нотации, применявшейся в работе [ ], m обозначает среднюю длину входных строк, а n – суммарный размер входных данных задачи.
 
Здесь <math>d_H(s, s'_i)</math> обозначает расстояние Хэмминга между s и si0, т. е. количество позиций, в которых s и <math>s'_i</math> различаются. Согласно нотации, применявшейся в работе [7], m обозначает среднюю длину входных строк, а n – суммарный размер входных данных задачи.




Irina
4446

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/14303