4 ms·
Simple regexes can be reasonably quick, but you're almost certainly never going to do better than linear time, and if you get fancy, it's easy to go exponential
by throwanem 10y ago
Simple regexes can be reasonably quick, but you're almost certainly never going to do better than linear time, and if you get fancy, it's easy to go exponential with a large exponent.
- deleted 10y ago[deleted]
- pjscott 10y agoIf you want to guarantee that this will never happen, RE2 and similar regular expression engines are guaranteed to run in O(n) time, where n is the length of the target string. https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/ I've had nothing but good experiences with it. (Rust's looks similar, by the way, and quite impressive.)
- burntsushi 10y agoIndeed. Rust's regex engine is descended from RE2. rsc's blog posts were my guide when I first wrote it.