What is the time complexity, space complexity and algorithm for strstr () function in C ++?

Question

I was interested to learn about the cost of using the default strstr () static function in C ++. What is its complexity in time and space? What algorithm does he use? We have other algorithms with the smallest time and spatial complexity: Let n = line length, m = picture length

• Knuth-Morris-Pratt Algorithm: Time = O (n + m), Space = O (m)
• Rabin-Karp algorithm: Time = O (n * m), Space = O (p) (p = p patterns of combined length m)
• Boyer-Moore algorithm: Time = O (n * m), Space = O (S) (S = character set size) Is strstr () anyway better than the above algorithms in terms of the complexity of time and space?

Answer 1

In the C standard, he simply says, in §7.24.5.7:

Summary

#include <string.h> char *strstr(const char *s1, const char *s2); 

Description

The strstr function finds the first occurrence in the string pointed to by s1 sequences of characters (excluding the terminating null character) in the string pointed to by s2.

Return

The strstr function returns a pointer to the located string, or a null pointer if the string is not found. If s2 points to a string with zero length, the function returns s1.

Thus, the complexity is not defined. As far as I can tell, implementations are allowed to use any of these algorithms.

Answer 2

Well, it depends entirely on the environment. AFAIK MSVC runtime makes strstr the most naive way in O (n * m) complexity. But brute force does not require additional memory space, so it never raises a bad alloc exception. KMP requires O (m) extra space, and Two-Way requires constant extra space.

What GCC makes sounds is the same as using FFT to calculate multiplications. It looks very fast in paper, but actually very slow. MSVC will use the SIMD instructions in strstr when they are available, so in most cases they will be faster. I will choose a brute force approach with SIMD if I am going to write my own library.