2 ms·
There are some more gotchas. The finite state automata can potentially be exponential in the size of the regular expression you feed it. (Its states are set o
by btilly 10y ago
There are some more gotchas.
The finite state automata can potentially be exponential in the size of the regular expression you feed it. (Its states are set of states in the NFA.) Subexpression matching is more complex to implement and can make that exponential superexponential. (You have to go from sets of states to ordered sets of states.)
And these catastrophic expressions get much easier when you add in lookaheads, look behinds, and so on.