[nitely]

FWIW, nim-regex does achieve linear time in the rebar test[0], even if the regex includes capture groups. It's NFA based.

[0]: https://github.com/BurntSushi/rebar/pull/20#issuecomment-256...

[ieviev]

Oh that is interesting! I haven't even looked Nim regex until now, is it similar to the approach in Go?

[nitely]

It's similar to RE2, but it lacks the on the fly DFA, ie: it's just the classic Thompson's NFA with some tweaks. It does not implement find all the same way, though.