guarantee worst-case linear time matching for any
    number of expressions

Or you could just use RE2: https://github.com/google/re2/wiki/WhyRE2

It's open source, and match time is linear in the length of the input string.

(Disclosure: I work at Google on a different open source project)

RE2 is great! I first discovered it while building namegrep.com and after benchmarking it against PCRE I never looked back. :)

Interesting. We worked in this area for many years, did the 'startup' in this area, now acquired by Intel, open sourced the product (ob plug: https://github.com/01org/hyperscan ) and I would never claim that we are anything near 'solving' regex.

More like "mitigating" or "occasionally getting regex slightly more right than some other solutions". There are many different approaches to regex and all seem to focus on different parts of functionality (RE2 focuses on quick compiles and simplicity, libpcre has 'all the functionality', we're about streaming + large scale + high performance if you can tolerate long compiles and lots of complexity). A number of new projects are trying very interesting approaches, like icgrep and the Rust regex guys.

I would be curious to hear about your approach.