Re: `completion-in-region'

[Stefan Monnier <monnier@iro.umontreal.ca>]

>>>> If you use ".*?a.*?b.*?c", then yes it gives the
>>>> same matches but it also has the same O(N^3) worst case.
>>> This is not the right place perhaps to educate me on this, but to me
>>> it looks like just three linear searches with the summed length for
>>> the searches equal to that of the candidate strings. Is not that O(N)?
>> When matched against "ababab", it will do the following:
>> - search for a in the string.
>> - for each match of a, search for b in the remaining string.
> I do not understand the "for each" here. I thought that since ".*?" is
> greedy that means that only the first "a" could match.

No, what the question mark means is that it will first try to match the
first a, rather than first try to match the last a.

Fundamentally, our | is an ordered alternation operator (i.e. first try
the lefthand side and if that fails, try the righthandside), and the
repetition operators are defined as:

   E*  = (EE*|)
   E*?   (|EE*?)


-- Stefan