#! perl -slw
use strict;
use constant MINMATCH => 3;

## returns a list of 3 integers.
## offset into the haystack
## offset into the needle ( can be negative, subtract from length(needle) )
## length of match.
sub search {
    my( $haystack, $needle, $pos ) = @_;
    my( @start, @end );
    my $l = length $needle;

    ## A full match found
    return( $pos-1, 0, $l ) if $pos = 1+index $haystack, $needle;

    ## iterate, and attempt matches at both ends
    for( 1 .. $l-1 ) {
        my $r = $l - $_;   ## reverse offset

        last if $r < MINMATCH; ## quit if we've reached the minimum match length

        ## try a partial match at the beginning
        substr( $haystack, $_-$l ) eq substr( $needle, 0, $l-$_ )
            and @start = ( length( $haystack )-( $l-$_), -$_, $l-$_  );

        ## try a partial match at the end
        substr( $haystack, 0, $r ) eq substr( $needle, -$r )
            and @end = ( 0, $_, $r );

        ## Quit if we got either.
        last if @start or @end;
    }
    return        unless @start or @end;  ## No match
    return @start unless @end;            ## No partial at the end, start is best
    return @end   unless @start;          ## No partial at the start, end is best
    return $start[2] >= $end[2] ? @start : @end; ## Got both, longest (or start if equal) is best
}

our @haystacks = (
    'TTGTCAGCGAAAAAAATTAAAGCGCAAGATTGTTGGTTTTTGCGTGATGGTGACCGGGCAGCCTAAAGGCTATCCTTAACCAGGGAGCTGATT',
    'GAATGTTTTAGCAATCTCTTTCTGTCATGAATCCATGGCAGTGACCATACTAATGGTGACTGCCATTGATGGAGGGAGACACAGTGCACTGGCAAACTCACAC',
    'TAATCAAAACCAATAAACACGAAATAATCCCCATGCCGGTGAAGAAGGGGCGTGACTTTAGCGAAATGTTGCCGTCGCGACAACCGGAATATGAAAGCAAAGCGCAGCGTCTGAATAACGTTTATGCTGAAAGCGGATGAATAAGGAGATGCG',
);
our @needles = (
    'GCGAAAAAAATTAAAGCGCAAGATTGTTGGTTTTTGCGTGATGGTGAC',
    'CATTACATTGCTGGATAAGAATGTTTTAGCAATCTCTTTCTGTCATGA',
    'CGCGACAACCGGAATATGAAAGCAAAGCGCAGCGTCTGAATAACGTTT',
);

$, = ' ';
for my $needle ( @needles ) {
    for my $haystack ( @haystacks ) {
        my( $hOffset, $nOffset, $l ) = search $haystack, $needle;
        if( defined $hOffset ) {
            print "$hOffset, $nOffset, $l";
            printf "%s%s\n%s%s\n\n",
                ' 'x$nOffset, $haystack,
                ' 'x$hOffset, $needle;
        }
        else {
            print "No match found in '$haystack'\n for '$needle'\n";
        }
    }
}

__END__
C:\test>579215-2
6, 0, 48
TTGTCAGCGAAAAAAATTAAAGCGCAAGATTGTTGGTTTTTGCGTGATGGTGACCGGGCAGCCTAAAGGCTATCCTTAACCAGGGAGCTGATT
      GCGAAAAAAATTAAAGCGCAAGATTGTTGGTTTTTGCGTGATGGTGAC

No match found in 'GAATGTTTTAGCAATCTCTTTCTGTCATGAATCCATGGCAGTGACCATACTAATGGTGACTGCCATTGATGGAGGGAGACACAGTGCACTGGCAAACTCACAC'
 for 'GCGAAAAAAATTAAAGCGCAAGATTGTTGGTTTTTGCGTGATGGTGAC'

150, -45, 3
TAATCAAAACCAATAAACACGAAATAATCCCCATGCCGGTGAAGAAGGGGCGTGACTTTAGCGAAATGTTGCCGTCGCGACAACCGGAATATGAAAGCAAAGCGCAGCGTCTGAATAACGTTTATGCTGAAAGCGGATGAATAAGGAGATGCG
                                                                                                                                                      GCGAAAAAAATTAAAGCGCAAGATTGTTGGTTTTTGCGTGATGGTGAC

No match found in 'TTGTCAGCGAAAAAAATTAAAGCGCAAGATTGTTGGTTTTTGCGTGATGGTGACCGGGCAGCCTAAAGGCTATCCTTAACCAGGGAGCTGATT'
 for 'CATTACATTGCTGGATAAGAATGTTTTAGCAATCTCTTTCTGTCATGA'

0, 18, 30
                  GAATGTTTTAGCAATCTCTTTCTGTCATGAATCCATGGCAGTGACCATACTAATGGTGACTGCCATTGATGGAGGGAGACACAGTGCACTGGCAAACTCACAC
CATTACATTGCTGGATAAGAATGTTTTAGCAATCTCTTTCTGTCATGA

No match found in 'TAATCAAAACCAATAAACACGAAATAATCCCCATGCCGGTGAAGAAGGGGCGTGACTTTAGCGAAATGTTGCCGTCGCGACAACCGGAATATGAAAGCAAAGCGCAGCGTCTGAATAACGTTTATGCTGAAAGCGGATGAATAAGGAGATGCG'
 for 'CATTACATTGCTGGATAAGAATGTTTTAGCAATCTCTTTCTGTCATGA'

No match found in 'TTGTCAGCGAAAAAAATTAAAGCGCAAGATTGTTGGTTTTTGCGTGATGGTGACCGGGCAGCCTAAAGGCTATCCTTAACCAGGGAGCTGATT'
 for 'CGCGACAACCGGAATATGAAAGCAAAGCGCAGCGTCTGAATAACGTTT'

No match found in 'GAATGTTTTAGCAATCTCTTTCTGTCATGAATCCATGGCAGTGACCATACTAATGGTGACTGCCATTGATGGAGGGAGACACAGTGCACTGGCAAACTCACAC'
 for 'CGCGACAACCGGAATATGAAAGCAAAGCGCAGCGTCTGAATAACGTTT'

75, 0, 48
TAATCAAAACCAATAAACACGAAATAATCCCCATGCCGGTGAAGAAGGGGCGTGACTTTAGCGAAATGTTGCCGTCGCGACAACCGGAATATGAAAGCAAAGCGCAGCGTCTGAATAACGTTTATGCTGAAAGCGGATGAATAAGGAGATGCG
                                                                           CGCGACAACCGGAATATGAAAGCAAAGCGCAGCGTCTGAATAACGTTT