import java.util.regex.*;

public class catastrophic {
    public static void main(String[] args) {
        for (int runs = 0; runs < 2; runs++) {
            //Pattern pattern = Pattern.compile("(0*)*A");
            //Pattern pattern = Pattern.compile("a?{20}a{20}");

            // Run from 5 to 25 characters
            for (int length = 5; length < 30; length++) {
                Pattern pattern = Pattern.compile("(a*)*b");
                // 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");
            }
        }
    }
}