Posts Implement strstr (geeksforgeeks - SDE Sheet)
Post
Cancel

Implement strstr (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

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.

geeksforgeeks

SOLUTION

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
class GfG
{
    int strstr(String s, String x)
    {

        // Start from index 0 of string s
        int idx = 0;

        // If the length of x is greater than s, x cannot be a substring of s.
        if(x.length() > s.length())
            return -1;

        // Iterate through string s using idx as the starting index
        while(idx < s.length()){

            // Check if the current character in s matches the first character of x
            if(s.charAt(idx) == x.charAt(0)){

                // Pointer for s starting from current index idx
                // Pointer for x starting from the beginning
                int i = idx;
                int j = 0;

                // Check subsequent characters in both strings
                while(i < s.length() && j < x.length()){

                    // If characters do not match, break out of the loop
                    if(s.charAt(i) != x.charAt(j))
                        break;

                    i++;  // Move to next character in s
                    j++;  // Move to next character in x

                }

                // If we have compared all characters of x (j == x.length()),
                // it means x is found in s starting from index idx
                if(j == x.length())
                    // Return the starting index of the found substring
                    return idx;

            }

            // Increment idx to check for the substring from the next character in s
            idx++;

        }

        // If the loop completes without returning, x was not found in s
        return -1;
    }
}

THIS CAN ALSO BE SOLVED USING RABIN KARP ALGORITHM

This post is licensed under CC BY 4.0 by the author.