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 = "neveropen" Output: 5 Explanation: String "for" is present as a substring of s2. Input: s1 = "practice", s2 = "neveropen" Output: -1. Explanation: There is no occurrence of "practice" in "neveropen"
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.
PHP
<?php // PHP program to check if a // string is substring of other. // Returns true if s1 is substring // of s2 function isSubstring($s1, $s2) { $M = strlen($s1); $N = strlen($s2); // A loop to slide // pat[] one by one for ($i = 0; $i <= $N - $M; $i++) { $j = 0; // For current index i, // check for pattern match for (; $j < $M; $j++) if ($s2[$i + $j] != $s1[$j]) break; if ($j == $M) return $i; } return -1; } // Driver Code $s1 = "for"; $s2 = "neveropen"; $res = isSubstring($s1, $s2); if ($res == -1) echo "Not present"; else echo "Present at index " . $res; // This code is contributed by mits ?> |
Output:
Present at index 5
Complexity Analysis:
- Time complexity: O(m * n) where m and n are lengths of s1 and s2 respectively.
A nested loop is used the outer loop runs from 0 to N-M and inner loop from 0 to M so the complexity is O(m*n). - Space Complexity: O(1).
As no extra space is required.
An efficient solution is to use a O(n) searching algorithm like KMP algorithm, Z algorithm, etc.
Please refer complete article on Check if a string is substring of another for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
