string::find complexity.

[Matt Austern]

On Jun 9, 2004, at 11:05 PM, Dhruv Matani wrote:

> Hello,
> 	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?

There are really two questions here.
  (1) Why is string::find implemented from scratch, instead of just
         implemented as a thin wrapper around std::search()?
  (2) Why doesn't either of them use KMP?

The answer to the first question: no good reason that I can think
of.  std::string::find and std::search both do substring matches.
It shouldn't be implemented twice.  Doing it once means that
whatever bug fixes and performance tweaks you make apply
in more places.

The answer to the second question: Alex Stepanov deliberately
decided to use a worst-case-quadratic algorithm for std::search,
instead of KMP, because he believed that the quadratic case
was rare in practice and that in typical cases the worst-case-
quadratic algorithm was faster.  The last time anyone tried to
measure this (this was work by Dave Musser and John
Wilkinson, maybe five years ago), they found that Alex was right.
But they also found that there were some clever performance
improvements that would make substring matching even faster.
Those improvements are there in std::search but not in the
simple hand-written std::string::find.

So my advice: rewrite std::string::find so that it uses search.
You'll have to use the version that takes a function object,
of course, because of the traits template parameter.  Don't
rewrite std::search in terms of KMP unless you have numbers
to prove that it's always an improvement---and I think you won't
find that.  If you want to implement KMP then implement it as
a separate algorithm that people can use when they care more
about worst-case complexity than about complexity in the
common case.

			--Matt