diff -r 4110ab35e5d8 -r 25bc57b32efa progs/catastrophic.java --- 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 +}