Hello.

Couple of days ago I was solving this stringy problem from codeforces contest -> http://codeforces.com/contest/832/problem/B.

After I solved it using regexes, I wanted to find others who approached same way, and only I've found was solution in Ruby. And the maximum time for any test case with mine solution was about 3x slower than with contestants' who used Ruby.
Time-limit: 2000 ms; Memory Limit: 256 MB;
Here are two links for solutions:
Ruby - http://codeforces.com/contest/832/submission/28852992
Perl - http://codeforces.com/contest/832/submission/28885266
I can see 94 test cases, but sadly - not whole but only pieces of them.
TC #84:
Perl: Time: 997 ms, memory: 3180 KB
Ruby: Time: 77 ms, memory: 12304 KB
TC #93:
Perl: Time: 171 ms, memory: 21796 KB
Ruby: Time: 311 ms, memory: 42948 KB
(about 15-50 ms are used anytime solving any TC)

Both solutions seem similar. Except of chomping or not chomping input lines (which also can influence speed). Both solutions compile final regex before use it over next n (1 ≤ n ≤ 10e5) query strings. During contest I haven't compiled regex and got time-limit-exceeded >2000 ms comparing to 93 ms with compiled (qr//) regex (at TC #47).

I can't see whole TC #84, but logically it contains 4 lines: 
b
*aaaaa...
1
...aaaaa...

[download]
where triple points means sequence of some symbols.
Here I hardcoded one of possible variants which takes some hundreds ms to complete: 
#!/usr/bin/perl

use warnings;
use strict;

$\ = $/;

    my $dict = 'b';
    $_ = '*' . 'a' x (9e4 - 1e4) . "\n";
    
    s/\?/[$dict]/g;
    s/\*/[^$dict]*/;
    
    my $qr = qr/^$_$/;
    
    print $_ =~ $qr ? "YES" : "NO" for 'a' x (0 + 1e4) . 'a' x (9e4 - 
+1e4) . "\n";

[download]


So what is the worst test case for mine solution? Is there a better solution using regex? Why is such difference between Perl and Ruby at 84th TC?

Upd. Codeforces is using Perl 5.20.1, -> problemset -> custom-test.
To find other solutions of this problem, you go to problem -> status, and setup "status filter".

In reply to the case where regex seems to work slower by rsFalse

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.