From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: `completion-in-region' Date: Mon, 12 Apr 2010 09:10:36 -0400 Message-ID: References: <493575A8A83B43BCB1AF49E239599A77@us.oracle.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1271077940 29016 80.91.229.12 (12 Apr 2010 13:12:20 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 12 Apr 2010 13:12:20 +0000 (UTC) Cc: Leo , Drew Adams , emacs-devel@gnu.org To: Lennart Borgman Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Apr 12 15:12:18 2010 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1O1JR2-00008l-Rr for ged-emacs-devel@m.gmane.org; Mon, 12 Apr 2010 15:12:17 +0200 Original-Received: from localhost ([127.0.0.1]:35100 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O1JR2-0006sI-5z for ged-emacs-devel@m.gmane.org; Mon, 12 Apr 2010 09:12:16 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1O1JPY-0006KX-Oc for emacs-devel@gnu.org; Mon, 12 Apr 2010 09:10:44 -0400 Original-Received: from [140.186.70.92] (port=52499 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1O1JPW-0006K9-64 for emacs-devel@gnu.org; Mon, 12 Apr 2010 09:10:44 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1O1JPS-0006fk-Ft for emacs-devel@gnu.org; Mon, 12 Apr 2010 09:10:42 -0400 Original-Received: from ironport2-out.teksavvy.com ([206.248.154.183]:11753 helo=ironport2-out.pppoe.ca) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1O1JPS-0006fR-DB for emacs-devel@gnu.org; Mon, 12 Apr 2010 09:10:38 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvsEAP64wktMCqWu/2dsb2JhbACbMXK6QIUMBItG X-IronPort-AV: E=Sophos;i="4.52,190,1270440000"; d="scan'208";a="60662504" Original-Received: from 76-10-165-174.dsl.teksavvy.com (HELO pastel.home) ([76.10.165.174]) by ironport2-out.pppoe.ca with ESMTP; 12 Apr 2010 09:10:37 -0400 Original-Received: by pastel.home (Postfix, from userid 20848) id 9CC9D7F1B; Mon, 12 Apr 2010 09:10:36 -0400 (EDT) In-Reply-To: (Lennart Borgman's message of "Mon, 12 Apr 2010 11:46:33 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:123517 Archived-At: >>>> 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