#/usr/bin/perl
use strict;
use warnings;

sub match{
    my ( $text, $regexp ) = @_;
    my @text = split //,$text;
    my @regexp = split //,$regexp;
    
    if ( $regexp[0] eq '^' ){
        shift @regexp;
        return matchhere( \@regexp, \@text );
    }
    do{
        return 1 if matchhere(\@regexp, \@text);
    } while (shift @text);
    return 0;
}

sub matchhere{
    my ($regexp_ref, $text_ref) = @_;
    if( @$regexp_ref == 0){
        return 1;
    }
    if( $regexp_ref->[1] and $regexp_ref->[1] eq '*' ){
        my @tmp = @{$regexp_ref}[2..$#$regexp_ref];
        return matchstar( $regexp_ref->[0], \@tmp, $text_ref );
    }
    if( $regexp_ref->[0] eq '$' ){
        return @$text_ref ? 0 : 1;
    }
    if( (@$text_ref != 0) && ($regexp_ref->[0] eq '.' || 
                              $regexp_ref->[0] eq $text_ref->[0] ) ){
        my @tmp1 = @{$regexp_ref}[1..$#$regexp_ref];
        my @tmp2 = @{$text_ref}[1..$#$text_ref];
        return matchhere( \@tmp1, \@tmp2 );
    }
    return 0;
}

sub matchstar{
    my ($char, $regexp_ref, $text_ref ) = @_;
    my $i = 0;
    do{
        return 1 if matchhere($regexp_ref, $text_ref);
    }while ( $char eq shift @$text_ref || $char eq '.');
    return 0;
}

print match('hoaaaaaaaaaaaaaaaaaadd', '^hoa*dd$');