pcre, bifs, drivers and ports

Mats Cronqvist <>
Thu Aug 3 10:47:05 CEST 2006


Richard A. O'Keefe wrote:
> Mats Cronqvist <> wrote:
> 	   but as far as i understand (from googling) the time is bounded by k*M*N, 
> 	where M is the length of the string and N is the length of the regexp. so by 
> 
> Is this so?  Matching a string against a finite state automaton
> is linear, but I thought turning a regular expression into a finite state
> automaton is exponential.  Certainly the classic RE -> NFA -> FA method
> is exponential.

   if it's on the internet, it must be true :>

http://perl.plover.com/NPC

   mats



More information about the erlang-questions mailing list