3 ms·
It also ignores rsc's clear algorithmic preferences. No, RE2 does not support back-references, because they require a back-tracking implementation with exponent
by jonstewart 8y ago
It also ignores rsc's clear algorithmic preferences. No, RE2 does not support back-references, because they require a back-tracking implementation with exponential worst-case behavior. RE2 uses an NFA with O(nm) worst-case behavior. It's a classical Unix approach where a simple implementation is preferable to having more features, especially if there are algorithmic considerations.