// 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 -> to warmup of the JVM+ −
for (int runs = 0; runs < 2; runs++) {+ −
+ −
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"; }+ −
+ −
// Measure the average duration of two calls... + −
long start = System.nanoTime();+ −
for (int i = 0; i < 2; i++) {+ −
pattern.matcher(input).find();+ −
}+ −
+ −
// Print out time+ −
System.out.println(length + " " + input + ": " + −
+ ((System.nanoTime() - start) / 2000000000d) + −
+ "s");+ −
}+ −
}+ −
}+ −
} + −