This seems to work. Run it on a terminal 100+ wide to see the output properly; the wrapping screws it up.

#! perl -slw
use strict;

sub search {
    my( $haystack, $needle, $pos ) = @_;
    my $l = length $needle;
    my( @res1, @res2 );

    return( $pos-1, 0, $l ) if $pos = 1+index $haystack, $needle;

    substr( $haystack, 0, $_ ) eq substr( $needle, -$_ )
        and @res1 = ( 0, $l-$_, $_ ), last
        for reverse 1 .. $l-1;

    substr( $haystack, $_-$l ) eq substr( $needle, 0, $l-$_ )
        and @res2 = ( length( $haystack )-( $l-$_), -$_, $l-$_  ), las
+t
        for 1 .. $l-1;

    return       unless @res1 or @res2;
    return @res1 unless @res2;
    return @res2 unless @res1;
    return $res1[2] > $res2[2] ? @res1 : @res2;
}

my $haystack = 'GAATGTTTTAGCAATCTCTTTCTGTCATGAATCCATGGCAGTGACCATACTAAT
+GGTGACTGCCATTGATGGAGGGAGACACA';
my @needles = (
    'NOT FOUND',
    'CTGGATAAGAATGTTTTAGCAATCTCTT',
    'CTGCCATTGATGGAGGGAGACACAACGTACGT',
    'CATGAATCCATGGCAGTGACCATACTAATGGTGACTG',
    'AGGGAGACACAGAATGTTTTAG',
    'AGGGAGACACAGAATGTTTTAGC',
);

$, = ' ';
for my $needle ( @needles ) {
    my( $hOffset, $nOffset, $l ) = search $haystack, $needle;
    print "No match found in '$haystack'\n for '$needle'\n"
        and next unless defined $hOffset;

    printf "%s%s\n%s%s\n\n",
        ' 'x$nOffset, $haystack,
        ' 'x$hOffset, $needle;
}
__END__
c:\test>579215
No match found in 'GAATGTTTTAGCAATCTCTTTCTGTCATGAATCCATGGCAGTGACCATACT
+AATGGTGACTGCCATTGATGGAGGGAGACACA'
 for 'NOT FOUND'

        GAATGTTTTAGCAATCTCTTTCTGTCATGAATCCATGGCAGTGACCATACTAATGGTGACTG
+CCATTGATGGAGGGAGACACA
CTGGATAAGAATGTTTTAGCAATCTCTT

GAATGTTTTAGCAATCTCTTTCTGTCATGAATCCATGGCAGTGACCATACTAATGGTGACTGCCATTGAT
+GGAGGGAGACACA
                                                           CTGCCATTGAT
+GGAGGGAGACACAACGTACGT

GAATGTTTTAGCAATCTCTTTCTGTCATGAATCCATGGCAGTGACCATACTAATGGTGACTGCCATTGAT
+GGAGGGAGACACA
                         CATGAATCCATGGCAGTGACCATACTAATGGTGACTG

GAATGTTTTAGCAATCTCTTTCTGTCATGAATCCATGGCAGTGACCATACTAATGGTGACTGCCATTGAT
+GGAGGGAGACACA
                                                                      
+  AGGGAGACACAGAATGTTTTAG

           GAATGTTTTAGCAATCTCTTTCTGTCATGAATCCATGGCAGTGACCATACTAATGGTGA
+CTGCCATTGATGGAGGGAGACACA
AGGGAGACACAGAATGTTTTAGC
[download]