#StackBounty: #ds.algorithms #regular-expressions #string-matching #string-search #search-engines Match a string agains a set of regexes

Bounty: 100

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.


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.