What is the Time Complexity, Space complexity and Algorithm for strstr() function in C++?

Question

I was curious about the cost of using the default, old fashioned strstr() function in C++. What is its Time and Space complexity? Which algorithm does it use? We have other algorithms with below Worst Case Time and Space complexity : Let n = length of string, m = length of pattern

1. Knuth-Morris-Pratt Algorithm : Time = O(n+m), Space = O(m)
2. Rabin-Karp Algorithm : Time = O(n*m), Space = O(p) (p = p patterns of combined length m)
3. Boyer-Moore Algorithm : Time = O(n*m), Space = O(S) (S = size of character set) In any way strstr() is better than above mentioned algorithms, in terms of Time and Space complexities?

Delicatessen

Basically, it's not specified. Not a very satisfactory answer, I know. Do you have a specific implementation you want to know about? – Instil

I meant a specific implementation of the function, or C standard library. For instance, the one in Gnu libc, or the one used by MS Visual Studio, or some other one? – Instil

Sorry.. I dont have any BoB.. – Delicatessen

glibc is using KMP, see strstr.c source file, although it is modified with some sse2 optimizations. – Kanara

Answer 1

In the C standard it just says, in §7.24.5.7:

Synopsis

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

Description

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

Returns

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.

So the complexity is unspecified. As far as I can tell, an implementation is allowed to use any of those algorithms.

Sunsunbaked