#!/usr/bin/env ruby

# A case of catastrophic backtracking in Ruby
#---------------------------------------------
# example provided by Daniel Baldwin
#
# 
# regex: (a?){n} a{n}
# strings: aa...
#
# run on the command line with:
#
# ./catastrophic.rb
#

nums = (1..30)

#iterate through the nums 1-30
nums.each do |i|

	start_time = Time.now
	string = "a" * i

        #create a new regular expression based on current value of i
	re_str = "a?" * i + "+" + "a" * i
	re = Regexp.new(re_str)

        re.match(string)

        #if re.match(string)
	#	puts "matched string  a * #{i} with regex #{re}"
	#else
	#	puts "unmatched string a * #{i} with regex #{re}"
	#end
	
  puts "#{i} %.5f" % (Time.now - start_time)
end