# A case of catastrophic backtracking in Ruby

#---------------------------------------------

#

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

# strings: aa...

#

# example provided by Daniel Baldwin

#

# call with:

#

#   > ruby catastrophic.rb

#

nums = (1..1000)

#iterate through the nums 1-1000

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