Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re^4: Compare two regex patterns

by Anonymous Monk
on Mar 23, 2008 at 00:39 UTC ( [id://675703]=note: print w/replies, xml ) Need Help??


in reply to Re^3: Compare two regex patterns
in thread Compare two regex patterns

you can build the minimal DFA (that can be done in O(n²) or O(n³), not sure...)

Actually that can be done in O(n lg n) using Hopcroft's Algorithm, but it's not a well known or particularly easy algorithm. See Hopcroft's 1971 paper, though even the academics find it a bit dense, which led Gries to write a paper called Describing an algorithm by Hopcroft a year later. Unfortunately the latter is not freely available online.

All this is surely overboard for the poster's original question, I just wanted to share this tidbit since it's not easy to come by.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://675703]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others goofing around in the Monastery: (5)
As of 2024-03-29 14:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found