From owner-freebsd-hackers  Mon Oct  1 22:44:30 2001
Delivered-To: freebsd-hackers@freebsd.org
Received: from ajax.cnchost.com (ajax.cnchost.com [207.155.248.31])
	by hub.freebsd.org (Postfix) with ESMTP id 0D93E37B411
	for <freebsd-hackers@freebsd.org>; Mon,  1 Oct 2001 22:44:29 -0700 (PDT)
Received: from bitblocks.com (adsl-209-204-185-216.sonic.net [209.204.185.216])
	by ajax.cnchost.com
	id BAA28358; Tue, 2 Oct 2001 01:44:24 -0400 (EDT)
	[ConcentricHost SMTP Relay 1.14]
Message-ID: <200110020544.BAA28358@ajax.cnchost.com>
To: "Andrew L. Neporada" <andrew@nas.dgap.mipt.ru>
Cc: freebsd-hackers@freebsd.org
Subject: Re: current strstr(3) implementation is slow 
In-reply-to: Your message of "Tue, 02 Oct 2001 08:32:12 +0400."
             <Pine.BSF.4.21.0110020807550.33266-100000@nas.dgap.mipt.ru> 
Date: Mon, 01 Oct 2001 22:44:24 -0700
From: Bakul Shah <bakul@bitblocks.com>
Sender: owner-freebsd-hackers@FreeBSD.ORG
Precedence: bulk
List-ID: <freebsd-hackers.FreeBSD.ORG>
List-Archive: <http://docs.freebsd.org/mail/> (Web Archive)
List-Help: <mailto:majordomo@FreeBSD.ORG?subject=help> (List Instructions)
List-Subscribe: <mailto:majordomo@FreeBSD.ORG?subject=subscribe%20freebsd-hackers>
List-Unsubscribe: <mailto:majordomo@FreeBSD.ORG?subject=unsubscribe%20freebsd-hackers>
X-Loop: FreeBSD.ORG

> 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.

To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message