4 ms·
A non-backtracking regex engine like re2 should be linear with respect to the regex size and can be configured with a memory budget.
by lilyball 7y ago
A non-backtracking regex engine like re2 should be linear with respect to the regex size and can be configured with a memory budget.
- wahern 7y agoThe number of DFA states can explode exponentially. It's a real problem, especially if you're compiling untrusted expressions off the internet. Evaluation is linear, but you're just evaluating your own password. In this scenario, it may make sense to just use a simple backtracking implementation, though as you alluded to early there aren't many simple ones around.
- pjscott 7y agoRE2, at least, will fall back to an NFA-based matcher if things get too pathological.