Самый быстрый способ найти минимальное расстояние Хэмминга до любой подстроки?
Учитывая длинную строкуL
и более короткая строкаS
(ограничение заключается в том, чтоL
длина должна быть & gt; =S
.length), я хочу найти минимальное расстояние Хемминга междуS
и любая подстрокаL
с длиной, равнойS
.length. Давайте вызовем функцию для этогоminHamming()
, Например,
minHamming(ABCDEFGHIJ, CDEFGG) == 1
.
minHamming(ABCDEFGHIJ, BCDGHI) == 3
.
Выполнение этого очевидным способом (перечисление каждой подстроки L) требует O (S
длина *L
. длина) время. Есть ли какой-нибудь умный способ сделать это в сублинейное время? Я ищу то же самоеL
с несколькими разнымиS
Строки, делая некоторую сложную предварительную обработкуL
один раз приемлемо
Редактировать: модифицированный Бойер-Мур был бы хорошей идеей, за исключением того, что мой алфавит состоит всего из 4 букв (ДНК).