Given two strings s1 and s2, find if s1 is a substring of s2. If yes, return the index of the first occurrence, else return -1.
Examples :
Input: s1 = "for", s2 = "geeksforgeeks"
Output: 5
Explanation:
String "for" is present as a substring
of s2.
Input: s1 = "practice", s2 = "geeksforgeeks"
Output: -1.
Explanation:
There is no occurrence of "practice" in
"geeksforgeeks"
Simple Approach: The idea is to run a loop from start to end and for every index in the given string check whether the sub-string can be formed from that index. This can be done by running a nested loop traversing the given string and in that loop run another loop checking for sub-string from every index.
For example, consider there to be a string of length N and a substring of length M. Then run a nested loop, where the outer loop runs from 0 to (N-M) and the inner loop from 0 to M. For very index check if the sub-string traversed by the inner loop is the given sub-string or not.
// C++ program to check if a string is // substring of other. #include <bits/stdc++.h> using namespace std; // Returns true if s1 is substring // of s2 int isSubstring(string s1, string s2) { int M = s1.length(); int N = s2.length(); /* A loop to slide pat[] one by one */ for (int i = 0; i <= N - M; i++) { int j; /* For current index i, check for pattern match */ for (j = 0; j < M; j++) if (s2[i + j] != s1[j]) break; if (j == M) return i; } return -1; } // Driver code int main() { string s1 = "for"; string s2 = "geeksforgeeks"; int res = isSubstring(s1, s2); if (res == -1) cout << "Not present"; else cout << "Present at index " << res; return 0; }
Output:
Present at index 5
Complexity Analysis:
An efficient solution is to use a O(n) searching algorithm like KMP algorithm, Z algorithm, etc.
Language implementations:
Another Efficient Solution:
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; int Substr(string s2, string s1) { // pointing s2 int counter = 0; int i = 0; for(; i < s1.length(); i++) { if(counter==s2.length()) break; if(s2[counter]==s1[i]) { counter++; } else { // Special case where character preceding // the i'th character is duplicate if(counter > 0) { i -= counter; } counter = 0; } } return (counter < s2.length() ? -1 : i - counter); } // Driver code int main() { string s1 = "geeksfffffoorrfoorforgeeks"; cout << Substr("for", s1); return 0; } // This code is contributed by Manu Pathria
Output:
18
The complexity of the above code will be still O(n*m) in the worst case and the space complexity is O(1).
Australia
UK
UAE
Singapore
Canada
New
Zealand
Malaysia
USA
India
South
Africa
Ireland
Saudi
Arab
Qatar
Kuwait
Hongkong
Copyright 2016-2023 www.programmingshark.com - All Rights Reserved.
Disclaimer : Any type of help and guidance service given by us is just for reference purpose. We never ask any of our clients to submit our solution guide as it is, anywhere.