# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1486551710 0
# Node ID 4bdf0dedd708986d79025a411b04da6b2e7ba0e9
# Parent  dc528091eb70536d6be0295c0472dbaa0459ea2d
updated

diff -r dc528091eb70 -r 4bdf0dedd708 progs/catastrophic.java
--- a/progs/catastrophic.java	Sat Jan 21 00:25:09 2017 +0000
+++ b/progs/catastrophic.java	Wed Feb 08 11:01:50 2017 +0000
@@ -8,7 +8,7 @@
 public class catastrophic {
     public static void main(String[] args) {
 
-        //we always run all the tests twice -> warmup of the JVM
+        //we always run all the tests twice -> to warmup of the JVM
         for (int runs = 0; runs < 2; runs++) {
             
             Pattern pattern = Pattern.compile("(a*)*b");
@@ -25,7 +25,8 @@
                 for (int i = 0; i < 2; i++) {
                     pattern.matcher(input).find();
                 }
-                
+
+                // Print out time
                 System.out.println(length + " " + input + ": " 
                        + ((System.nanoTime() - start) / 2000000000d) 
                        + "s");
diff -r dc528091eb70 -r 4bdf0dedd708 progs/catastrophic.rb
--- a/progs/catastrophic.rb	Sat Jan 21 00:25:09 2017 +0000
+++ b/progs/catastrophic.rb	Wed Feb 08 11:01:50 2017 +0000
@@ -2,18 +2,19 @@
 
 nums = (1..1000)
 
-#iterate through the nums 1-100
+#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
-	#create a new regular expression based on current value of i
-	
 	re = Regexp.new(re_str)
 
         re.match(string)
-	#if re.match(string)
+
+        #if re.match(string)
 	#	puts "matched string  a * #{i} with regex #{re}"
 	#else
 	#	puts "unmatched string a * #{i} with regex #{re}"
diff -r dc528091eb70 -r 4bdf0dedd708 progs/catastrophic3.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/catastrophic3.py	Wed Feb 08 11:01:50 2017 +0000
@@ -0,0 +1,24 @@
+#!/usr/bin/env python
+import re
+import sys
+
+# case of catastrophic backtracking in Python
+#
+# regex: (a?){n} a{n}
+# strings: aa...
+#
+# call with timing as:
+#
+#   > time ./catastrophic.py 20
+
+# counter n given on the command line
+cn = sys.argv[1]
+
+# constructing the regex
+r = '(.*)a(.{%s})bc' % cn
+
+# calling the matching function
+#m = re.match(r, "axaybzbc") 
+m = re.match(r, "a" * 100 + "a" * int(cn) + "bc") 
+
+print m.group(0)