RE2 approach only supports actual regular expressions (no backreferences or other horrors) and has an O(n) time complexity guarantee. Can also make an efficient search index.
https://codesearch.debian.net is based on the indexing approach/code from the 4th post in that series. Try it.