ChrisK wrote:
If you need to be left-biased then you need a perl-style engine, and you can use the regex-pcre or pcre-light haskell package and the PCRE library. These are obtainable from Hackage. I doubt PCRE uses a simple DFA...
I don't know if regex-pcre or pcre-light supports the (?{...})-ism of Perl 5.6 and above, but if it does then it's fairly easy to implement the trie automaton I mentioned in my previous post: just add a (?{ $value = ... }) action to the end of each component regex and read out the value of $value after you match. You'll still want to run the automata through a minimizer/optimizer after gluing all the components together, otherwise you still get O(n) behavior since you don't share the work for common prefixes. -- Live well, ~wren