I checked a pathological case and with binary search found a slow combination:

$h='U*e?Z+';
$s='0Yh7rrt1d22BCpt5j62OMASaLznTPG947Ucl9pbtBq7Ab7U26cgrSKUOlKSRLABnre
+6nyw4IglTZW';
[download]

Substituting 'U' or 'e' doesn't matter much, but 'Z' is important since it is in the string far at the end. Other values like 'M' would produce somewhat faster results, and 'F' (which is not in the string at all) is really fast again.

Sadly I don't have a perl with debugging compiled in and don't see why this pattern should be so slow.

Playing with a fast example showed that eliminating + subpatterns at the start of the pattern got to pathological cases relatively fast. So it is more surprising that the majority of random patterns do NOT exhibit the slow matching