Very interesting. That is much more sophisticated than what I'm doing. My literal extraction is a simple greedy approach on the AST that only finds prefixes. My "scoring" is just a silly heuristic at this point. I had been doing it on the NFA itself, but found the AST easier to work with.

I think my problem is that I don't know how to take interior literals or suffix literals and apply them to search without provoking worst case quadratic behavior. For example, take the regex `\w+\s+Holmes`. It's easy enough to find `Holmes` and do a fast literal search for it. Then you can match `\w+\s+` in reverse from the start of the literal hit. But whoops, `Holmes` is a substring in the set of all strings described by `\w+\s+`, which means your automaton can start re-scanning input you've already seen. In pathological cases, you get quadratic behavior. (Similar to a poorly written Boyer-Moore implementation.)

I wonder if this gets easier using hyperscan's "all-matches" semantics. I haven't given alternative matching semantics much thought yet.

> We'd love help working on this problem (hey, we're open source) but Building Your Own regex engine seems to be the thing everyone must do. It's probably a lot more fun than trying to grab a tractable bit to work on in a 100+Kloc source base.

Yeah, I started on Rust's regex engine almost 2 years ago. It's been a labor of love.