Dada uma longa stringL e uma corda menorS (a restrição é queLComprimento deve ser> =S(comprimento), eu quero encontrar a distância mínima de Hamming entreS e qualquer substring deL com comprimento igual aS.comprimento. Vamos chamar a função para issominHamming(). Por exemplo,

minHamming(ABCDEFGHIJ, CDEFGG) == 1.

minHamming(ABCDEFGHIJ, BCDGHI) == 3.

Fazer isso da maneira mais óbvia (enumerando cada substring de L) requer O (S.comprimento *Ltempo de duração. Existe alguma maneira inteligente de fazer isso no tempo sublinear? Eu procuro o mesmoL com vários diferentesS strings, fazendo assim algum pré-processamento complicado paraL uma vez é aceitável.

Edit: O Boyer-Moore modificado seria uma boa idéia, exceto que meu alfabeto é de apenas 4 letras (DNA).