lets go explicit, the following (halting!) counterexamples use fairly short input strings and fairly simple regexes, nevertheless resulting in exploding run times...

perl -e '
for $n(10..14) {
  $str = "x"x($n*2+1); 
  $t=time;
  $str =~ /(x+x+){$n}y/;
  print "\$str:$str n:$n time:",time-$t,"sec\n"
}'
$str:xxxxxxxxxxxxxxxxxxxxx n:10 time:0sec
$str:xxxxxxxxxxxxxxxxxxxxxxx n:11 time:3sec
$str:xxxxxxxxxxxxxxxxxxxxxxxxx n:12 time:9sec
$str:xxxxxxxxxxxxxxxxxxxxxxxxxxx n:13 time:39sec
$str:xxxxxxxxxxxxxxxxxxxxxxxxxxxxx n:14 time:156sec
[download]

I hope it's now obvious that an empiric brute force approach can only (if ever) work with rigid restrictions!

(credits go to ratazong for finding the base principle in this example after some /msging and credits to his unwillingness to post it afterwards ... ;)

UPDATE: improved code...

UPDATE just for fun :)

perl -e '
for $n(1..14) {
  $str = "x"x($n*3+1); 
  $t=time;
  $str =~ /(x+x+x+){$n}y/;
  print "\$str:$str n:$n time:",time-$t,"sec\n"
}'
$str:xxxx n:1 time:0sec
$str:xxxxxxx n:2 time:0sec
$str:xxxxxxxxxx n:3 time:0sec
$str:xxxxxxxxxxxxx n:4 time:0sec
$str:xxxxxxxxxxxxxxxx n:5 time:0sec
$str:xxxxxxxxxxxxxxxxxxx n:6 time:0sec
$str:xxxxxxxxxxxxxxxxxxxxxx n:7 time:1sec
$str:xxxxxxxxxxxxxxxxxxxxxxxxx n:8 time:9sec
$str:xxxxxxxxxxxxxxxxxxxxxxxxxxxx n:9 time:73sec
$str:xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx n:10 time:555sec
^C
[download]