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]:





map[0:0 7:2]