use strict;
use warnings;

$a = 'ATGGAGTCGACGAATTTGAAGAAT';
$b = 'xxxxxxATGGAGyxxxTCGAzxxxxCGAATTTGAAxxwGAAT';

my $prevPos = 0;
my $reA = createRegex($a);
while ($b =~ /$reA/g) {
	my $match = $&;
	my $skipped = substr($`, $prevPos);
	print "[$skipped]\n";
	$a = substr($a, length($match));
	last if length($a) == 0;
	$prevPos = pos($b);
	$reA = createRegex($a);
}

sub createRegex {
	my ($str) = @_;
	my @chars = split(//, $str);
	my $firstChar = shift(@chars);
	my $re = '';
	foreach my $char (reverse @chars) {
		$re = '(?:' . $char . $re . ')?';
	}
	return $firstChar . $re;
}