Most likely, the difference comes when one regex engine is backtracking to ultimately fail.

I'm not sure what the exact problem description is, but maybe you can speed things up by making some match fails not greedy or atomic (or both). Maybe the following fails faster:

s/\*/[^$dict]*?/g
[download]

Or maybe the following replacement makes things fail faster, as it prevents backtracking over that group if it ever failed.:

s/\*/(?>[^$dict]*)/g
[download]

(As a note, your second replacement has no /g flag while the Ruby code uses .gsub in both cases)

while (my $dict = <>) {
    chomp $dict;
    my $nodict = join q(), 'a' .. 'z';
    $nodict =~ s/[$dict]//g;

    $_ = <>;
    s/\?/[$dict]/g;
    s/\*/[$nodict]*/;
[download]

($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord
}map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,
[download]

Just fudge things a little :)

#!/usr/bin/perl

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

use strict;
use warnings;

$\ = $/;

my $dict = 'b';
$_ = '*' . 'a' x (9e4 - 1e4) . "\n";

my($head, $tail) = map length( $_ // '' ), split /\*/, $_;

s/\?/[$dict]/g;
s/\*/ [^$dict ]* /;

my $qr = qr/^$_$/;

substr($_, $head, 0, ' '),
  substr($_, -$tail, 0, ' '),
  print $_ =~ $qr ? "YES" : "NO"
    for 'a' x (0 + 1e4) . 'a' x (9e4 - 1e4) . "\n";
[download]

This avoids the massive backtrack this particular problem encounters.

I think this do not work at cases when '*' is absent or not in the middle!
Read more... (4 kB)

Hey, it worked for the test case you gave :)

(grumble, grumble, inadequate test cases :( Even these test cases are inadequate, can you figure out why? )

#!/usr/bin/perl

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

use strict;
use warnings;

$\ = $/;

while(<DATA>)
  {
  chomp;
  my $dict = $_;

  $_ = <DATA>;

  my($head, $tail) = map length( $_ // '' ), split /\*/;

  s/\?/[$dict]/g;
  s/\*/ [^$dict ]* /;

  my $qr = qr/^$_/;

  $_ = <DATA>,
    $head <= length($_) && substr($_, $head, 0, ' '),
    $tail && $tail <= length($_) && substr($_, -$tail, 0, ' '),
    print $_ =~ $qr ? "YES" : "NO"
      for 1 .. <DATA>;
  }

__DATA__
ab
a?a
3
aaa
aab
aaac
ab
*a?a
3
aaa
aab
caaa
ab
a?a*
3
aaa
aab
aaac
b
aaaaaaaaaaaaaaaaaaaaaaa*aaaaaaaaaaaaaaaaaa
1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
b
aaaaaaaaaaaaaaaaaaaaaaa*aaaaaaaaaaaaaaaaaa
1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
b
*aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
b
*aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa*
1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa*
1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
b
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
[download]