--- 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");
--- 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}"
--- /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)