This will knock the spots of most every other algorithm implemented in perl and many of them when implemented in C:

#! perl -slw
use strict;

sub fuzzyMatch {
    my( $rHay, $rNee, $misses ) = @_;
    my $lNee = length $$rNee;
    my $min = $lNee - $misses;

    map {
        (
            ( substr( $$rHay, $_, $lNee ) ^ $$rNee
        ) =~ tr[\0][] ) >= $min ? $_ : ()
    } 0 .. length( $$rHay ) - $lNee;
}

my $hay = 'TCGAGTGGCCATGAACGTGCCAATTG';
my $nee =           'ATGATCCTG';

print substr( $hay, $_-5, length( $nee ) + 10 ) for fuzzyMatch( \$hay,
+ \$nee, 3 );

$hay = 'aacctgacctacgtttgacgatcgtacgtcagtcctccgtgctaactgacgtaaaaaaaata
+cgtcccccccc';
$nee = 'acgtacgt';

print substr( $hay, $_-5, length( $nee ) + 10 ) for fuzzyMatch( \$hay,
+ \$nee, 3 );

__END__
C:\test>1048594
TGGCCATGAACGTGCCAAT
acctgacctacgtttgac
gacctacgtttgacgatc
gtttgacgatcgtacgtc
gacgatcgtacgtcagtc
atcgtacgtcagtcctcc
gtcagtcctccgtgctaa
tgctaactgacgtaaaaa
aactgacgtaaaaaaaat
aaaaaaaatacgtccccc
aaaatacgtcccccccc
[download]

The subroutine returns the offset where the fuzzily matched substrings are found in the primary; one for each match.