Geek Answers Handbook

Algorithm: The intersection of two regular expressions

I would like to find out (at runtime) whether two regular expressions intersect (i.e. if they exist, there is one or more lines that match as regular expressions).

The algorithm should be pretty fast as I need to scroll through the database and check for existing values.

Found some theory about this, but no realizations?

+3
source share
3 answers

The obvious solution would be to convert the regular expressions to DFA, calculate the DFA intersection (trivial) and see if there is anything that the resulting DFA can accept (also trivial). The only tricky part is converting regular expressions to DFA, which requires some work.

+3
source

This is where the implementation in Haskell runs using partial derivatives of regular expressions. Commentary on this post indicates a problem with approaching Chris Dodd.

+3
source

How about checking the first and then the other with the input that passed the first?

0
source

More articles:


All Articles