There are several algorithms to match a (simple) string against a regular expression (see here). But if we have a lot of regexes, can we find one of them that matches the given string faster than checking the string with all of the regexes, one by one?
For example, if we have $k$ regexes, each with a length of $m$ and a string of length $n$, using the $O(mn)$ algorithm to match a string with a regex $k$ times gives us a running time of $O(kmn)$. Can we do better than this?
If you have an answer which requires some assumptions, please explicitly tell them.