pcre, bifs, drivers and ports

Richard A. O'Keefe ok@REDACTED
Thu Aug 3 01:07:44 CEST 2006


Mats Cronqvist <mats.cronqvist@REDACTED> 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.




More information about the erlang-questions mailing list