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