Implement strstr() function in C (Iterative & Recursive)
Write an efficient program to implement strstr function in C. The strstr() function returns a pointer to the first occurrence of a string in another string.
The prototype of the strstr() is:
const char* strstr(const char* X, const char* Y);
1. Iterative Implementation
Following’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(m.n) where m and n are the length of String X and Y, respectively.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <stdio.h> // returns true if `X` and `Y` are the same int compare(const char *X, const char *Y) { while (*X && *Y) { if (*X != *Y) { return 0; } X++; Y++; } return (*Y == '\0'); } // Function to implement `strstr()` function const char* strstr(const char* X, const char* Y) { while (*X != '\0') { if ((*X == *Y) && compare(X, Y)) { return X; } X++; } return NULL; } // Implement `strstr()` function in C int main() { char *X = "Techie Delight - Ace the Technical Interviews"; char *Y = "Ace"; printf("%s\n", strstr(X, Y)); return 0; } |
Output:
Ace the Technical Interviews
2. Using memcmp() function
Following is strstr implementation using memcmp() function defined in code. The time complexity of this solution remains O(m.n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <stdio.h> // Function to implement `strstr()` function const char *strstr(const char *X, const char *Y) { size_t n = strlen(Y); while (*X) { if (!memcmp(X, Y, n)) { return X; } X++; } return 0; } // Implement `strstr()` function in C int main() { char *X = "Techie Delight – Ace the Technical Interviews"; char *Y = "Ace"; printf("%s\n", strstr(X, Y)); return 0; } |
Output:
Ace the Technical Interviews
3. 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 the length of the strings X and Y, respectively.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <stdio.h> // Function to implement `strstr()` function using KMP algorithm const char* strstr(const char* X, const char* Y, int m, int n) { // base case 1: `Y` is NULL or empty if (*Y == '\0' || n == 0) { return X; } // base case 2: `X` is NULL, or X's length is less than Y's if (*X == '\0' || n > m) { return NULL; } // `next[i]` stores the index of the next best partial match int next[n + 1]; for (int i = 0; i < n + 1; i++) { next[i] = 0; } for (int i = 1; i < n; i++) { int j = next[i + 1]; while (j > 0 && Y[j] != Y[i]) { j = next[j]; } if (j > 0 || Y[j] == Y[i]) { next[i + 1] = j + 1; } } for (int i = 0, j = 0; i < m; i++) { if (*(X + i) == *(Y + j)) { if (++j == n) { return (X + i - j + 1); } } else if (j > 0) { j = next[j]; i--; // since `i` will be incremented in the next iteration } } return NULL; } // Implement `strstr()` function in C int main(void) { char *X = "Techie Delight – Ace the Technical Interviews"; char *Y = "Ace"; printf("%s\n", strstr(X, Y, strlen(X), strlen(Y))); return 0; } |
Output:
Ace the Technical Interviews
That’s all about strstr() implementation in C.
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)