From: w_a_x_man <w_a_x_man@...>
Date: 2009-08-01T01:30:07+09:00
Subject: Slow regular-expression engine

This Awk  code takes less than one hundredth of a second to run:

BEGIN {

  regex = \
    "o?o?o?o?o?o?o?o?o?o?o?o?o?o?" \
    "o?o?o?o?o?o?o?o?o?o?o?o?o?" \
    "ooooooooooooooooooooooooooooo"

  print "ooooooooooooooooooooooooooooo" ~ regex

}


This Ruby code takes 27.5 seconds:

t = Time.now

regex = Regexp.new(
  "o?o?o?o?o?o?o?o?o?o?o?o?o?o?" +
  "o?o?o?o?o?o?o?o?o?o?o?o?o?" +
  "ooooooooooooooooooooooooooooo" )

p "ooooooooooooooooooooooooooooo" =~ regex

puts "#{ Time.now - t } seconds"


See http://swtch.com/~rsc/regexp/regexp1.html