#!perl
# simulate the regexp /(a(?:|(?1)|a(?1)))/
use warnings; 
use strict;
for my $MEM (0, 1) { 
        print $MEM ? "with" : "without", " memoization\n"; 
        my $u;
        my %c = (); 
        my $f; $f = sub { 
                $u++; 
                my $a = join(",", @_); 
                $MEM and exists($c{$a}) and 
                        return $c{$a}; 
                $c{$a} = (
                        1 <= @_ and
                        $_[0] eq "a" and (
                                1 == @_ or
                                &$f(@_[1 .. @_ - 1]) or 
                                $_[1] eq "a" and 
                                        &$f(@_[1 .. @_ - 1])
                        )
                );
        }; 
        for my $s ("aaaaaaaa", "aaaaaaaab") { 
                $u = 0;
                print "  ", $s, ": ",
                        &$f($s =~ /(.)/g) ? "hit" : "miss", ", sub called ", $u, 
" times\n"; 
        } 
}
__END__