// A case of catastrophic backtracking in Java 9+

//------------------------------------------------

//

// It is actually not too bad in comparison what Python

// and Java 8 are to compute. But it is still pretty

// bad, even in Java 9, considering that the the basic

// part of the CW improves on this by a factor of 100

// (...if implemented correctly).

//

// regexp: (a*)*b

// strings: aa....aaa

//

// compile with: javac catastrophic9.java

// call with:    java catastrophic9

//

//

import java.util.regex.*;

public class catastrophic9 {

    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 = 0; length < 50000; length += 5000) {

                // 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 + " a's : " 

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

                       + " secs");

            }

        }

    }

}