1 # A case of catastrophic backtracking in Ruby

     2 #---------------------------------------------

     3 # example provided by Daniel Baldwin

     4 #

     5 # 

     6 # regex: (a?){n} a{n}

     7 # strings: aa...

     8 #

     9 # run on the command line with:

    10 #

    11 # $>  ruby catastrophic.rb

    12 #

    13 

    14 nums = (1..1000)

    15 

    16 #iterate through the nums 1-1000

    17 nums.each do |i|

    18 

    19 	start_time = Time.now

    20 	string = "a" * i

    21 

    22         #create a new regular expression based on current value of i

    23 	re_str = "a?" * i + "+" + "a" * i

    24 	re = Regexp.new(re_str)

    25 

    26         re.match(string)

    27 

    28         #if re.match(string)

    29 	#	puts "matched string  a * #{i} with regex #{re}"

    30 	#else

    31 	#	puts "unmatched string a * #{i} with regex #{re}"

    32 	#end

    33 	

    34   puts "#{i} %.5f" % (Time.now - start_time)

    35 end