Match a string agains a set of regexes 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.
Hyperscan is a high-performance multiple regex matching library that uses hybrid automata techniques to allow simultaneous matching of large numbers of regular expressions across streams of data. They explained their approach here:
https://www.hyperscan.io/2015/10/20/match-regular-expressions
Apparently, they didn't find a fast algorithm (in the worst case) for this problem: &quot;We have not found a single, elegant automata approach that handles arbitrary regular expressions in arbitrary number&quot;. However, they used a lot of optimization which works well enough in practice.
I also believe that in the worst case, the given regular expressions can be so complex that no better solution exists.