It might be interesting to look at the re2 regex engine source code. They claim: "RE2 is a fast, safe, thread-friendly alternative to backtracking regular expression engines like those used in PCRE, Perl, and Python. It is a C++ library".
They also have a link to a page about implementing regular expressions efficiently:
Probably worth checking out.
- Maxime