CODEWITHSUNDEEP
c++algorithmstring-search
Prasath Govind
Prasath Govind

Reputation: 750

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

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?

Upvotes: 14

Views: 7859

Answers (1)

Shoe
Shoe

Reputation: 76260

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.

Upvotes: 8

Related Questions