This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.

Index Nav:	[Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav:	[Date Prev] [Date Next]	[Thread Prev] [Thread Next]
Other format:	[Raw text]

Re: string::find complexity.

From: Paolo Carlini <pcarlini at suse dot de>
To: Ian Lance Taylor <ian at wasabisystems dot com>
Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>
Date: Thu, 10 Jun 2004 18:03:55 +0200
Subject: Re: string::find complexity.
References: <1086847470.13398.8.camel@localhost.localdomain> <xypwu2fsany.fsf@miranda.boston.redhat.com> <m3d6472ytj.fsf@gossamer.airs.com>

Ian Lance Taylor wrote:

Of course, KMP is only a win when the length of the string is significantly greater than the length of the pattern.

... and, what happens when that't not true? Does it lose bad?

A partial KMP that is often effective in practice is to first search backward through the pattern for the last but one occurrence of the last character. Then check whether the last character matches. If it does, do a full comparison. If it doesn't, increment by the distance between the last character and the immediately previous occurrence--the length of the pattern if you are lucky.

Thanks. By the way, there are good expositions of the algorithm around:

http://www.ics.uci.edu/~eppstein/161/960227.html

Paolo.

Follow-Ups:
- Re: string::find complexity.
  - From: Ian Lance Taylor

References:
- string::find complexity.
  - From: Dhruv Matani
- Re: string::find complexity.
  - From: Jason Merrill
- Re: string::find complexity.
  - From: Ian Lance Taylor

Index Nav:	[Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav:	[Date Prev] [Date Next]	[Thread Prev] [Thread Next]