Implement strstr() function in C (Iterative & Recursive)

Write an efficient program to implement strstr function in C. strstr() function returns a pointer to the first occurrence of a string in another string.

 
 

The prototype of strstr is:

const char* strstr(const char* X, const char* Y);

 

1. Iterative Implementation

Below’s iterative implementation of the strstr() function. It returns a pointer to the first occurrence of Y in X, or a null pointer if Y is not part of X. The time complexity of this solution is O(mn) where m and n are length of String X and Y respectively.

 

Download   Run Code

Output:

Coding made easy

 

2. Recursive Implementation

Below is recursive Implementation of above code. The time complexity of this solution remains O(mn) but it also uses extra space for call stack.

 

Download   Run Code

Output:

Coding made easy

 

3. Using memcmp() function

Below is strstr implementation using memcmp() function defined in code. The time complexity of this solution remains O(mn).

 

Download   Run Code

Output:

Coding made easy

 

4. Using KMP Algorithm (Efficient)

 
We can even use KMP Algorithm to solve this problem which offers O(m + n) complexity where m and n are length of strings X and Y respectively.

 

Download   Run Code

Output:

Coding made easy

 
Also See: Implement strstr function in Java

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz