[johndough]

If the regex rules do not require backreferences, it should be possible to implement them in such a way that they run in constant time with respect to the number of rules.

[MaxBarraclough]

<pedantry> Regex with backreferences isn't really regex at all, in that it no longer corresponds to the regular languages. </pedantry>