# 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:+
−
#+
−
# $>  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+
−