string::find complexity.

Paolo Carlini pcarlini@suse.de
Thu Jun 10 16:26:00 GMT 2004


Ian Lance Taylor wrote:

>How bad is bad, and how much do we care?  There are certainly cases
>where KMP loses quite badly.  Consider a pattern of length 100 and
>text of length 101.  Suppose all the characters in the pattern are
>different.  If the pattern does not match at the head, the current
>algorithm does at most one extra compare.  With KMP you spend a lot of
>time building an automaton, and you still do one extra compare.  I'm
>sure the overall time would be much worse (especially in the micro
>benchmarks you've been using).
>
Thanks. We should really implement both the algorithm and your suggestion
and compare. Still, a linear complexity instead of a quadratic complexity
seems appealing...

About micro benchmarks... I'm reading a tad of irony in your remark...
well I don't think I had to trade so often a coefficient for an exponent,
for instance. If you have interesting larger scale testcases, would by
very welcome of course!

Thansk again,
Paolo.



More information about the Libstdc++ mailing list