Date: Tue, 2 Oct 2001 10:05:33 +0400 (MSD) From: "Andrew L. Neporada" <andrew@nas.dgap.mipt.ru> To: Bakul Shah <bakul@bitblocks.com> Cc: freebsd-hackers@freebsd.org Subject: Re: current strstr(3) implementation is slow Message-ID: <Pine.BSF.4.21.0110020948250.33545-100000@nas.dgap.mipt.ru> In-Reply-To: <200110020544.BAA28358@ajax.cnchost.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.BSF.4.21.0110020948250.33545-100000>