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.
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