If the possibility your describe can happen, I think this is a computationally simpler solution:

#! perl -slw
use strict;

my @queries = qw[ GCGAT CACGT ];

chomp( my @targets = <DATA> );

for my $q ( @queries ) {
    for my $t ( @targets ) {
        my $matched = ( $q ^ substr( $t, 0, length( $q ) ) ) =~ tr[\0]
+[\0];
        if(
            $matched == length( $q )
        or  $matched == length( $q )-1 
        and substr( $t, 0, length( $q ) ) =~ tr[N][N] == 1
        ) {
            print "$q matched $t";
        }
    }
}

__DATA__
GNGATNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
+NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
GCGANBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
+BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
CNCGTNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
+NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
GBGATNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
+NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
[download]