pcre, bifs, drivers and ports

Mats Cronqvist <>
Fri Aug 4 11:11:27 CEST 2006

Richard A. O'Keefe wrote:
> Bjorn Gustavsson <> wrote:
> 	Also, a FA can be difficult/impossible to use if you need to
> 	know exactly what part of the string matched, for instance if
> 	you need to replace the matched string with something else.
> There's a Master's thesis "Efficient Submatch Addressing for
> Regular Expressions" by one Laurikari from Finland which explains
> how to do exactly that (with a slightly modified form of NFA).

   he has an implementation too;


from the manual;

  "The algorithm uses linear worst-case time in the length of the text being 
searched, and quadratic worst-case time in the length of the used regular 
expression. In other words, the time complexity of the algorithm is O(M2N), 
where M is the length of the regular expression and N is the length of the text."


  "There is one exception: if back references are used, the matching may take 
time that grows exponentially with the length of the string. "


Premature optimization is the root of all evil in programming.
C. A. R. Hoare

More information about the erlang-questions mailing list