Date: Mon, 01 Oct 2001 22:44:24 -0700 From: Bakul Shah <bakul@bitblocks.com> To: "Andrew L. Neporada" <andrew@nas.dgap.mipt.ru> Cc: freebsd-hackers@freebsd.org Subject: Re: current strstr(3) implementation is slow Message-ID: <200110020544.BAA28358@ajax.cnchost.com> In-Reply-To: Your message of "Tue, 02 Oct 2001 08:32:12 %2B0400." <Pine.BSF.4.21.0110020807550.33266-100000@nas.dgap.mipt.ru>
next in thread | previous in thread | raw e-mail | index | archive | help
> 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200110020544.BAA28358>