// 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 < 3; runs++) {+
−
            +
−
            Pattern pattern = Pattern.compile("(a*)*b");+
−
            +
−
            // Run from 5 to 28 characters+
−
            for (int length = 70000; length < 70001; 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();+
−
                }+
−
                +
−
                System.out.println(length + " " + input + ": " +
−
                       + ((System.nanoTime() - start) / 3000000000d) +
−
                       + "s");+
−
            }+
−
        }+
−
    }+
−
} +
−
+
−
+
−
+
−
// javac catastrophic.java +
−
// java catastrophic+
−