If '*' is in the middle of string, it seems OK:

#!/usr/bin/perl

# http://perlmonks.org/?node_id=1196089

use warnings;
use strict;

$\ = $/;

while(<DATA>){
    chomp;
    my $dict = $_;
    $_ = <DATA>;
    
    my( $head, $tail ) = map length( $_ // '' ), split /\*/, $_;
    print "head:[$head], tail:[$tail]";
    
    s/\?/[$dict]/g;
    s/\*/[^$dict]*/;
    
    my $qr = qr/^$_$/;
    print "regex:[$qr]";
    
    (print "loop #:[$_]"),
        $_ = <DATA>, (print "[$_]"),
        substr($_, $head, 0, ' '), (print "[$_]"),
        substr($_, -$tail, 0, ' '), (print "[$_]"),
        print "Answer: ", $_ =~ $qr ? "YES" : "NO"
            for 1 .. <DATA>;
    }
    
__DATA__
ab
a?*a
2
aacca
aaccb
[download]

OUTPUT:

head:[2], tail:[2]
regex:[(?^:^a[ab][^ab]*a
$)]
loop #:[1]
[aacca
]
[aa cca
]
[aa cc a
]
Answer: YES
loop #:[2]
[aaccb
]
[aa ccb
]
[aa cc b
]
Answer: NO
[download]

If star is absent, output should contain "YES" and then "NO". Another __DATA__ for same code:

__DATA__
ab
a?a
2
aaa
aab
[download]

OUTPUT

head:[4], tail:[]
regex:[(?^:^a[ab]a
$)]
loop #:[1]
[aaa
]
[aaa
 ]
[ aaa
 ]
Answer: NO
loop #:[2]
[aab
]
[aab
 ]
[ aab
 ]
Answer: NO
[download]

But I understood idea, and after modified a bit. Added line #13, and changed lines #25-26, got OK:

#!/usr/bin/perl

# http://perlmonks.org/?node_id=1196089

use warnings;
use strict;

$\ = $/;

while(<DATA>){
    chomp;
    my $dict = $_;
    $_ = <DATA>;
    
    my $star = /\*/;
    my( $head, $tail ) = map length( $_ // '' ), split /\*/, $_;
    print "head:[$head], tail:[$tail]";
    
    s/\?/[$dict]/g;
    s/\*/[^$dict]*/;
    
    my $qr = qr/^$_$/;
    print "regex:[$qr]";
    
    (print "loop #:[$_]"),
        $_ = <DATA>, (print "[$_]"),
        $star && substr($_, $head, 0, ' '), (print "[$_]"),
        $star && substr($_, -$tail, 0, ' '), (print "[$_]"),
        print "Answer: ", $_ =~ $qr ? "YES" : "NO"
            for 1 .. <DATA>;
    }
    
__DATA__
ab
a?a
2
aaa
aab
[download]

OUTPUT:

head:[4], tail:[]
regex:[(?^:^a[ab]a
$)]
loop #:[1]
[aaa
]
[aaa
]
[aaa
]
Answer: YES
loop #:[2]
[aab
]
[aab
]
[aab
]
Answer: NO
[download]

But when trying to submit to codeforces, got Run-time error, seems because of star is at the end,
or at beginning of a string (http://codeforces.com/contest/832/submission/28928022 , TC #3).