Catastrophic or exponential backtracking
Regular expression engines can be broadly categorized into two types:
- The Non-deterministic Finite Automation (NFA) engine
- The Deterministic Finite Automation (DFA) engine
The DFA engines do not evaluate each character more than once to find a match. On the other hand, the NFA engines support backtracking, which means that each character in the input can be evaluated multiple times by the regex engine. The Java regular expression engine is an NFA engine.
Regex engines backtrack or give back one position at a time to make various attempts to match a given pattern when using the greedy quantifier or trying alternations. Similarly, when using lazy quantifiers, the regex engine moves forward one position at a time to attempt matching.
Regex engines usually take less time to find a positive match in the given input as compared to returning a failure for a non-match. The NFA regex engines need to evaluate all the possible permutations before returning a failure...
