pcre, bifs, drivers and ports

[Mats Cronqvist]

Richard A. O'Keefe wrote:
> Bjorn Gustavsson <bjorn@REDACTED> 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;

http://laurikari.net/tre/index.html

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. "

    mats

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