Skip to main content

Implement strstr

Problem​

Your task is to implement the function strstr. The function takes two strings as arguments (s,x) and locates the occurrence of the string x in the string s. The function returns an integer denoting the first occurrence of the string x in s (0 based indexing).

Note: You are not allowed to use inbuilt function.

Examples:​

Example 1:

Input:
s = GeeksForGeeks, x = Fr
Output: -1
Explanation: Fr is not present in the string GeeksForGeeks as substring.

Example 2:

Input:
s = GeeksForGeeks, x = For
Output: 5
Explanation: For is present as substring in GeeksForGeeks from index 5 (0 based indexing).

Your task:​

You don't have to take any input. Just complete the strstr() function which takes two strings str, target as an input parameter. The function returns -1 if no match if found else it returns an integer denoting the first occurrence of the x in the string s.

  • Expected Time Complexity: O(∣s∣∗∣x∣)O(|s|*|x|)
  • Expected Auxiliary Space: O(1)O(1)

Note : Try to solve the question in constant space complexity.

Constraints:​

  • 1<=∣s∣,∣x∣<=1001 <= |s|,|x| <= 100

Solution​

Python​

def strstr(s,x):
n, m = len(s), len(x)
if m == 0:
return 0
for i in range(n - m + 1):
if s[i:i + m] == x:
return i
return -1

Java​

int strstr(String s, String x) {
int n = s.length();
int m = x.length();
if (m == 0) {
return 0;
}
for (int i = 0; i <= n - m; i++) {
if (s.substring(i, i + m).equals(x)) {
return i;
}
}
return -1;
}

C++​

int strstr(string s, string x) {
int n = s.length();
int m = x.length();
if (m == 0) {
return 0;
}
for (int i = 0; i <= n - m; i++) {
if (s.substr(i, m) == x) {
return i;
}
}
return -1;
}

C​

int strstr_c(const char *s, const char *x) {
int n = strlen(s);
int m = strlen(x);
if (m == 0) {
return 0;
}
for (int i = 0; i <= n - m; i++) {
int match = 1;
for (int j = 0; j < m; j++) {
if (s[i + j] != x[j]) {
match = 0;
break;
}
}
if (match) {
return i;
}
}
return -1;
}
  • Time Complexity: O(∣s∣∗∣x∣)O(|s|*|x|)
  • Auxiliary Space: O(1)O(1)