StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<blockquote> <p>Why the c++'s implemented string::substr() doesn't use the KMP algorithm (and doesn't run in O(N + M)) and runs in O(N * M)?</p> </blockquote> <p>I assume you mean <code>find()</code>, rather than <code>substr()</code> which doesn't need to search and should run in linear time (and only because it has to copy the result into a new string).</p> <p>The C++ standard doesn't specify implementation details, and only specifies complexity requirements in some cases. The only complexity requirements on <code>std::string</code> operations are that <code>size()</code>, <code>max_size()</code>, <code>operator[]</code>, <code>swap()</code>, <code>c_str()</code> and <code>data()</code> are all constant time. The complexity of anything else depends on the choices made by whoever implemented the library you're using.</p> <p>The most likely reason for choosing a simple search over something like KMP is to avoid needing extra storage. Unless the string to be found is very long, and the string to search contains a lot of partial matches, the time taken to allocate and free that would likely be much more than the cost of the extra complexity.</p> <blockquote> <p>Is that corrected in c++0x?</p> </blockquote> <p>No, C++11 doesn't add any complexity requirements to <code>std::string</code>, and certainly doesn't add any mandatory implementation details.</p> <blockquote> <p>If the complexity of current substr is not O(N * M), what is that?</p> </blockquote> <p>That's the worst-case complexity, when the string to search contains a lot of long partial matches. If the characters have a reasonably uniform distribution, then the average complexity would be closer to <code>O(N)</code>. So by choosing an algorithm with better worst-case complexity, you may well make more typical cases much slower.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload