--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/catastrophic/catastrophic.rb Mon Jul 27 11:02:48 2020 +0100
@@ -0,0 +1,35 @@
+# 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