[tgammm]

You could certainly support some subset of regular expressions - e.g. prefixes or suffixes. You could also accelerate special cases by using that approach.

The fact is though, that searching a body of text with an arbitrary regular expression is an O(n) operation. And with the entire Web, O(n) is infeasible to do for every search. And it is O(n) only if you mean regular expression in the narrow technical sense. I believe that the best current algorithms for extended regular expressions (e.g. the ones in Perl) which support features like back-references are exponential in the worst case.