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|)$
• Expected Auxiliary Space: $O(1)$

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

Constraints:

• $1 <= |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|)$
• Auxiliary Space: $O(1)$