From owner-freebsd-hackers  Mon Oct  1 21:32:18 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 6FE7937B40C
	for <freebsd-hackers@freebsd.org>; Mon,  1 Oct 2001 21:32:15 -0700 (PDT)
Received: from localhost (andrew@localhost)
	by nas.dgap.mipt.ru (8.11.3/8.11.3) with ESMTP id f924WDb33388
	for <freebsd-hackers@freebsd.org>; Tue, 2 Oct 2001 08:32:13 +0400 (MSD)
	(envelope-from andrew@nas.dgap.mipt.ru)
Date: Tue, 2 Oct 2001 08:32:12 +0400 (MSD)
From: "Andrew L. Neporada" <andrew@nas.dgap.mipt.ru>
To: freebsd-hackers@freebsd.org
Subject: current strstr(3) implementation is slow
Message-ID: <Pine.BSF.4.21.0110020807550.33266-100000@nas.dgap.mipt.ru>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
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.

I'll send patches if you are interested.

				Andrey.


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