In [1]:
// Like the naive algorithm but we break out of the inner loop as soon as our
// mismatch budget exceeds the maximum allowed Hamming distance.
func naive_approx_hamming(p string, t string, maxHammingDistance int) map[int]int {
occurrences := make(map[int]int)
for i := 0; i < len(t) - len(p) + 1; i++ { // for all alignments
nmm := 0
for j := 0; j < len(p); j++ { // for all characters
if t[i+j] != p[j] { // does it match?
nmm += 1 // mismatch
if nmm > maxHammingDistance {
break // exceeded maximum distance
}
}
}
if nmm <= maxHammingDistance {
// approximate match; return pair where first element is the
// offset of the match and second is the Hamming distance
occurrences[i] = nmm
}
}
return occurrences
}
In [2]:
naive_approx_hamming("needle", "needle noodle nargle", 2)
Out[2]: