Re: the shorter the regexp, the longer the grep time

[Bill Rugolsky Jr.]

On Sat, Aug 16, 2003 at 02:38:45AM +0800, Dan Jacobson wrote:
> Gentlemen, what's the deal in that the shorter the regexp, the longer
> the grep time?

Probably because the algorithm is sub-linear.  By matching 
from right-to-left, one can jump ahead whenever one can
jump ahead large distances.  E.g., let char *s point to the current
position, then if s[8] is none of the characters in "fetchmail",
then we jump ahead nine positions, if it is 't', then we can jump ahead
six, etc.

Regards,

        Bill Rugolsky