From owner-freebsd-hackers Mon Oct 1 23: 5:44 2001 Delivered-To: freebsd-hackers@freebsd.org Received: from nas.dgap.mipt.ru (nas.dgap.mipt.ru [194.85.81.203]) by hub.freebsd.org (Postfix) with ESMTP id F423237B408 for ; Mon, 1 Oct 2001 23:05:40 -0700 (PDT) Received: from localhost (andrew@localhost) by nas.dgap.mipt.ru (8.11.3/8.11.3) with ESMTP id f9265YN33835; Tue, 2 Oct 2001 10:05:34 +0400 (MSD) (envelope-from andrew@nas.dgap.mipt.ru) Date: Tue, 2 Oct 2001 10:05:33 +0400 (MSD) From: "Andrew L. Neporada" To: Bakul Shah Cc: freebsd-hackers@freebsd.org Subject: Re: current strstr(3) implementation is slow In-Reply-To: <200110020544.BAA28358@ajax.cnchost.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG On Mon, 1 Oct 2001, Bakul Shah wrote: > > If the length of substring is M and the length of string is N, then > > current algorithm takes O(N*M) operations. > > It is possible to perform search faster -- O(N+M) operations only. > > Is this a known algorithm? If so which one? Note that > http://www-igm.univ-mlv.fr/~lecroq/string > is a pretty good reference on string matching. > Yes, this is known algorithm from Cormen, Leiserson, Rivest "Introduction to Algorithms" book (AKA CLR) by MIT Press, more precisely "Knuth, Morris and Pratt algorithm". Andrey. P.S. Very impressive URL! Thank you. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message