# 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.

• If the experience consists of finding if a string do match against each of the $k$ regexps and is rejected if it does not match against at least one of the $k$ regexps, then I have the intuition that one can reduce the variance of the computation durations of the experience by making the $k$ automatons process the string in a parallel way instead of sequencially one automaton after another. I follow this question and I'm quite interested in an answer too. – bonnal-enzo Jul 28 '20 at 15:50
• Intersection of regular languages is still regular, why don't you use the corresponding minimal automaton? – holf Jul 28 '20 at 16:22
• @holf Constructing the minimal intersection of $k$ DFA's requires $O(\exp(k))$ states in the worst case. – orlp Jul 28 '20 at 20:48
• @orlp it is not intersection - he's asking about the union – OrenIshShalom Aug 6 '20 at 17:36

The best strategy would be to simultaneously check the string against all DFA's. This is achieved by adding a new start vertex v0 and adding epsilon edges to the start vertices of all DFA's. Now you have an NFA. You can follow standard algorithms of determinizing it. This is exactly how automated lexer generators (like flex for example) work. Only instead of the input DFA's they have multiple regular expressions.
• Your solution does NOT provide a better running time (in comparison to $O(kmn)$). (I'm not the down-voter, by the way.) – Mohemnist Aug 7 '20 at 10:08