--- a/progs/catastrophic.java Wed Sep 14 16:51:04 2016 +0100
+++ b/progs/catastrophic.java Tue Sep 20 12:13:11 2016 +0100
@@ -1,14 +1,21 @@
+// a case of catastrophic backtracking in Java
+//
+// regexp: (a*)*b
+// strings: aa....
+
import java.util.regex.*;
public class catastrophic {
public static void main(String[] args) {
+
+ //we always run all the tests twice -> warmup of the JVM
for (int runs = 0; runs < 2; runs++) {
- //Pattern pattern = Pattern.compile("(0*)*A");
- //Pattern pattern = Pattern.compile("a?{20}a{20}");
-
- // Run from 5 to 25 characters
- for (int length = 5; length < 30; length++) {
- Pattern pattern = Pattern.compile("(a*)*b");
+
+ Pattern pattern = Pattern.compile("(a*)*b");
+
+ // Run from 5 to 28 characters
+ for (int length = 5; length < 28; length++) {
+
// Build input of specified length
String input = "";
for (int i = 0; i < length; i++) { input += "a"; }
@@ -18,10 +25,11 @@
for (int i = 0; i < 2; i++) {
pattern.matcher(input).find();
}
+
System.out.println(length + " " + input + ": "
+ ((System.nanoTime() - start) / 2000000000d)
+ "s");
}
}
}
-}
\ No newline at end of file
+}