pcre, bifs, drivers and ports
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