If you’ve ever done a lot of work with Regular Expressions, you’re probably familiar with the concept of catastrophic backtracking
, which means that the engine is forced to calculate permutations of exponential proportions. For instance, click here run this example
and see how long it takes (should be about 5-10 seconds to time out):
public class LongRunningRegexExample
public static void main(String args) throws InterruptedException
final Pattern pattern = Pattern.compile("(0*)*A");
final String input = "00000000000000000000000000";
long startTime = System.currentTimeMillis();
Matcher matcher = pattern.matcher(input);
matcher.find(); // runs for a long time!
System.out.println("Regex took:" + (System.currentTimeMillis() - startTime) + "ms");
However, a small change
results in near instantaneous response. Why?
For those of you who have not seen the Visual Regex Tester yet, this video should be informative, and for those of you who have, make sure to check out the new reverse-syntax highlighting features that I’ve recently added. My goal is to make this tester as useful and fun as possible; it should be a regular stable of regular expression development.