3 ms·
Doesn't that mean that you have exponential worst-case complexity?
by TheLoneWolfling 12y ago
Doesn't that mean that you have exponential worst-case complexity?
- jbnicolai 12y agoAbsolutely! Even worse, you may get different results than the expected method (FSA compilation) would yield. Observe: Javascript, executed in the console of a recent Chrome: > 'ab'.match(/a|ab/) ["a"] BSD Grep: > egrep 'a|ab' <<< ab ab
- TheLoneWolfling 12y agoYow... I was under the impression that all major regex engines used NFAs converted to DFAs lazily, with fallbacks to a slower engine for features that cannot (or cannot practically) be implemented using an NFA (unbounded backtracking, that sort of thing.) What is the advantage to doing this?