[Top][All Lists]

[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: Mon, 12 Apr 2010 11:46:33 +0200

On Mon, Apr 12, 2010 at 4:10 AM, Stefan Monnier
<address@hidden> wrote:
>>> 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.

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

> - for each match of b, search for c in the remaining string.
> These are 3 nested loops, each of them doing a number of iterations
> proportional to N, so you get O(N^3) complexity.
>        Stefan

reply via email to

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