Re: `completion-in-region'

["Davis Herring" <herring@lanl.gov>]

> I do not understand the "for each" here. I thought that since ".*?" is
> greedy that means that only the first "a" could match.

(Stefan spoke to this.)

> But maybe I am missing that the first ".*?" is not anchored. Would
> "^.*?a.*?b.*?c" behave differently?

You're right, actually, that this would help (though again the ?s are
irrelevant).  A search (as opposed to a match; `looking-at' is a match,
but (confusingly) `string-match' is a search) with the regexp ".*a.*b.*c"
will be O(N^4) in the length of the subject string because the search will
look for a c for each b match, a b for each a match, and an a for each
distance from the search point, and will search starting from each
position in the string.

Anchoring the search (which turns it into a match, effectively) removes
that last, outermost layer, and so reduces the complexity to N^3. 
However, I would implement this "fuzzy" search with just "a.*b.*c", which
has the same N^3 behavior without the "^.*" prefix that doesn't get you
anything.  (Of course, if it were implemented as a match, then the leading
.* would be necessary, the ^ would be superfluous, and the complexity
would still be N^3.)

Davis

-- 
This product is sold by volume, not by mass.  If it appears too dense or
too sparse, it is because mass-energy conversion has occurred during
shipping.