Angesichts einer langen SchnurL und eine kürzere SaiteS (Die Einschränkung ist, dassL. Länge muss> = seinS.length), möchte ich den minimalen Hamming-Abstand zwischen findenS und ein beliebiger Teilstring vonL mit einer Länge vonS.Länge. Nennen wir dazu die FunktionminHamming(). Zum Beispiel,

minHamming(ABCDEFGHIJ, CDEFGG) == 1.

minHamming(ABCDEFGHIJ, BCDGHI) == 3.

Wenn Sie dies auf die offensichtliche Weise tun (indem Sie jeden Teilstring von L aufzählen), benötigen Sie O (S. Länge *L.Länge) Zeit. Gibt es eine clevere Möglichkeit, dies in sublinearer Zeit zu tun? Ich suche das selbeL mit mehreren verschiedenenS Strings, so dass einige komplizierte Vorverarbeitung zu tunL einmal ist akzeptabel.

Bearbeiten: Die modifizierte Boyer-Moore wäre eine gute Idee, außer dass mein Alphabet nur 4 Buchstaben (DNA) ist.