1 // a case of catastrophic backtracking in Java

     2 //

     3 // regexp: (a*)*b

     4 // strings: aa....

     5 

     6 import java.util.regex.*;

     7 

     8 public class catastrophic {

     9     public static void main(String[] args) {

    10 

    11         //we always run all the tests twice -> warmup of the JVM

    12         for (int runs = 0; runs < 2; runs++) {

    13             

    14             Pattern pattern = Pattern.compile("(a*)*b");

    15             

    16             // Run from 5 to 28 characters

    17             for (int length = 5; length < 28; length++) {

    18                 

    19                 // Build input of specified length

    20                 String input = "";

    21                 for (int i = 0; i < length; i++) { input += "a"; }

    22                 

    23                 // Measure the average duration of two calls...  

    24                 long start = System.nanoTime();

    25                 for (int i = 0; i < 2; i++) {

    26                     pattern.matcher(input).find();

    27                 }

    28                 

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

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

    31                        + "s");

    32             }

    33         }

    34     }

    35 } 

    36 

    37 

    38 

    39 // javac catastrophic.java 

    40 // java catastrophic