New answers tagged

-1

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


1

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


Top 50 recent answers are included