emacs-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: `completion-in-region'


From: Lennart Borgman
Subject: Re: `completion-in-region'
Date: Sun, 11 Apr 2010 23:06:44 +0200

On Sun, Apr 11, 2010 at 10:51 PM, Stefan Monnier
<address@hidden> wrote:
>>> I see that ido implements it by turning "abc" into the regexp
>>> ".*a.*b.*c".  But matching this regexp against a string like
>>> "abababababab" takes time O(N^3) where N is the length of the completion
>>> candidate, which makes me a bit uneasy
>> Does not "^a.*?b.*?c" give the same matches?
>
> No because of the ^.

Eh, sorry.

> 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)?




reply via email to

[Prev in Thread] Current Thread [Next in Thread]