This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: string::find complexity.
Jason Merrill <jason@redhat.com> writes:
> On 10 Jun 2004 11:35:51 +0530, Dhruv Matani <dhruvbird@gmx.net> wrote:
>
> > I wanted to know why the string::find(string pos, n) function is
> > implemented as O(n^2), instead of the KMP algorithm which is much faster?
>
> Presumably because I wasn't aware of the KMP algorithm when I wrote the
> first implementation of the string class, and nobody has submitted a patch
> to improve it.
Of course, KMP is only a win when the length of the string is
significantly greater than the length of the pattern.
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.
Ian