This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: string::find complexity.
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.