Dada una larga cuerdaL y una cuerda más cortaS (la restricción es queL.length debe ser> =S.length), quiero encontrar la distancia mínima entre HammingS y cualquier subcadena deL con longitud igual aS.longitud. Llamemos a la función para esto.minHamming(). Por ejemplo,

minHamming(ABCDEFGHIJ, CDEFGG) == 1.

minHamming(ABCDEFGHIJ, BCDGHI) == 3.

Hacer esto de la manera obvia (enumerar cada subcadena de L) requiere O (S.longitud *L.length) tiempo. ¿Hay alguna forma inteligente de hacer esto en tiempo sublineal? Busco lo mismoL con varios diferentesS cuerdas, por lo que hacer un preprocesamiento complicado paraL una vez es aceptable.

Edit: El Boyer-Moore modificado sería una buena idea, excepto que mi alfabeto es de solo 4 letras (ADN).