Самый быстрый способ найти минимальное расстояние Хэмминга до любой подстроки?

Учитывая длинную строку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 букв (ДНК).

Ответы на вопрос(3)

Ваш ответ на вопрос