use v5.14;
use Data::Dump qw/pp/;

# In all this code the position 0 of an array of bits
# holds the rightmost bit in the string

# Finds the lowest position of a mismatch, or returns -1
sub match(++)
{
	for (0..$#{$_[0]})
	{
		return $_ if $_[0][$_] ne $_[1][$_];
	}
	return -1;
}

# Arrays of reversed bits ($haystack[0] is the rightmost bit of the bitstring)
my @haystack =  @ARGV ? reverse split //, shift : map { int rand 2 } 1..80;

# Unless the strings were specified by the user, take needle as part of the haystack
my $right = int(15 + rand 30);
my $len   = int(15 + rand 20); 
my @needle =    @ARGV ? reverse split //, shift : @haystack[$right..$right+$len];


# $pos[0] will contain the positions of 0 bits, and $pos[1] the positions of 1 bits 
my @pos = ([], []);

for (0..$#needle)
{
	push $pos[$needle[$_]], $_;
}

# Allow the bit beyond the length of needle to be either 1 or 0
push $pos[0], scalar @needle;
push $pos[1], scalar @needle;


pp @pos;

# If we are expecting bit B at position N but got !B
# the next occurence of !B in the needle will be
# $shift[N] bits to the left
my @shift;

for (0..$#needle) # For each bit in needle (from the right)
{
	my $bit = !$needle[$_];

	# Remove from @pos all reverse bits with a lower position
	shift $pos[$bit] while $pos[$bit][0] <= $_;

	# Push difference between the position of the next matching
	# bit and the position of the mismatch
	push @shift, $pos[$bit][0]-$_;
}

say "$_ => $shift[$_]" for 0..$#shift;

# Start with needle at the left
my $position = @haystack - @needle;

# If there is no match, a bruteforce solution will go through every
# position from the start
my $bruteforce = $position + 1;

my $needle = reverse @needle;
my $haystack = reverse @haystack;
my $steps = 0;

say "Needle should match at:", $position - $-[0] if $haystack =~ /$needle/;

while ($position >= 0)
{
	$steps++;
	my @substring = @haystack[$position..$position+$#needle];
	my $match = match @substring, @needle;
	last if $match < 0;
	$position -= $shift[$match]; 
}

say $haystack;
if ($position >= 0)
{
	say ' ' x (@haystack - @needle - $position), $needle;
	say "Match found at pos: $position";
	$bruteforce -= $position;
}
else
{
	say "No match found";
}

say "Steps needed: $steps";
say "Steps required for bruteforce: $bruteforce";