C++ string::find complexity

by

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)?

I assume you mean find(), rather than substr() 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).

The C++ standard doesn’t specify implementation details, and only specifies complexity requirements in some cases. The only complexity requirements on std::string operations are that size(), max_size(), operator[], swap(), c_str() and data() are all constant time. The complexity of anything else depends on the choices made by whoever implemented the library you’re using.

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.

Is that corrected in c++0x?

No, C++11 doesn’t add any complexity requirements to std::string, and certainly doesn’t add any mandatory implementation details.

If the complexity of current substr is not O(N * M), what is that?

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 O(N). So by choosing an algorithm with better worst-case complexity, you may well make more typical cases much slower.

More Related Contents:

  1. What is the difference between palindrome permutation and permutation? [closed]
  2. Replace part of a string with another string
  3. What is the fastest substring search algorithm?
  4. Replace substring with another substring C++
  5. Check if a string contains a string in C++
  6. How do I check if a C++ std::string starts with a certain string, and convert a substring to an int?
  7. Fast String Hashing Algorithm with low collision rates with 32 bit integer [closed]
  8. Splitting a string by a character
  9. How to use string.substr() function?
  10. Are there any better methods to do permutation of string?
  11. If strings are immutable in .NET, then why does Substring take O(n) time?
  12. Similar String algorithm
  13. How to remove all substrings from a string
  14. How to find and replace all occurrences of a substring in a string?
  15. What is the type of string literals in C and C++?
  16. Which is the fastest algorithm to find prime numbers?
  17. Why is strncpy insecure?
  18. How to remove certain characters from a string in C++?
  19. How do I concatenate multiple C++ strings on one line?
  20. String literal matches bool overload instead of std::string
  21. Error: invalid operands of types ‘const char [35]’ and ‘const char [2]’ to binary ‘operator+’
  22. Why are strings in C++ usually terminated with ‘\0’?
  23. invalid conversion from ‘const char*’ to ‘char’
  24. String to enum in C++
  25. writing directly to std::string internal buffers
  26. Generating m distinct random numbers in the range [0..n-1]
  27. C++: Can a macro expand “abc” into ‘a’, ‘b’, ‘c’?
  28. Do I have to use #include beside ?
  29. convert string to integer in c++
  30. What’s the difference between istringstream, ostringstream and stringstream? / Why not use stringstream in every case?

Leave a Comment