Podano długi sznurekL i krótszy sznurekS (ograniczeniem jest toL.length musi być> =S.length), chcę znaleźć minimalną odległość Hamminga międzyS i dowolny podciągL o długości równejS.długość. Wywołajmy tę funkcjęminHamming(). Na przykład,

minHamming(ABCDEFGHIJ, CDEFGG) == 1.

minHamming(ABCDEFGHIJ, BCDGHI) == 3.

Robiąc to w oczywisty sposób (wyliczając każdy podłańcuch L), wymaga O (S.length *L.length) time. Czy jest jakiś sprytny sposób na zrobienie tego w czasie sublinearnym? Szukam tego samegoL z kilkoma różnymiS łańcuchy, więc wykonuję skomplikowane wstępne przetwarzanieL raz jest dopuszczalne.

Edytuj: Zmodyfikowany Boyer-Moore byłby dobrym pomysłem, z wyjątkiem tego, że mój alfabet to tylko 4 litery (DNA).