Re: Possible problem with looking-back function

[Stephen J. Turnbull]

Andreas Röhler writes:

 > that surprises me.  Check must be done against the string already
 > found.  So workload should grow lineary resp. slightly ascending.

That's incorrect.  In regexp matching abstractly defined, there is no
"string already matched."  In general backtracking must be done to get
a correct POSIX match, and it's potentially very expensive.  It would
be sometimes possible (as in this case) to identify a non-backtracking
algorithm as you suggest, but that would mean that different regexps
would be treated differently, or that some regexps would be
ridiculously expensive.