in reply to the case where regex seems to work slower

With some inputs I created, avoiding the negated class sped the script about 2×, but it didn't improve your hardcoded testcase: 
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]

In Section Seekers of Perl Wisdom