#!/usr/local/bin/perl5
#
# Simple illustration of the Shift OR Algorithm
#
# M.W. Berry, CS494/594 Spring Semester 2003 
#
#--------------------------------------------------------------
# Assume 5 char pattern (5 states in NFA)
#
$state = 31;  # define initial state to be 11111 = 32
$text ="abdabababc";
#
# Pattern for matching is "ababc"
#
# Define bitmasks by hand here (would have to use separate module
#                               to compute via powers of 2)
%bitmask=(
          a => 26,
          b => 21,
          c => 15,
          d => 31
);
@chars=split(//,$text);

printf("State     Char\n");
printf(" %s    <init>\n",dec2bin($state));

while($next_char=<@chars>) {

  ($state <<= 1) -= 32;             # left shift and insert trailing zero
  $state |= $bitmask{$next_char};   # OR with current bitmask

  printf(" %s     %s\n",dec2bin($state), $next_char);
}

sub dec2bin {
    my $str = unpack("B32", pack("N", shift));
    $str =~ s/^0{27}(?=\d)//;
    return $str;
}