// 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 0 to 50000 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");
            }
        }
    }
}