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

                }

                System.out.println(length + " " + input + ": " 

                       + ((System.nanoTime() - start) / 2000000000d) 

                       + "s");

            }

        }

    }

} 

// javac catastrophic.java 

// java catastrophic