Implement strstr (Find Substring)

# Implement strstr (Find Substring) ## Difficulty Easy ## Tags `string`, `two pointers` ## Problem Statement Implement a function that finds the first occurrence of the substring `needle` in the string `haystack`. Return the index of the first character where the substring starts. If `needle` is not found in `haystack`, return `-1`. ## Constraints - If `needle` is an empty string, return `0`. - Both strings contain only lowercase English letters. - 0 ≤ haystack.length ≤ 10⁴ - 0 ≤ needle.length ≤ 10⁴ ## Signatures ### Python ```python def str_str(haystack: str, needle: str) -> int: pass ``` ### Java ```java public class Solution { public int str_str(String haystack, String needle) { return null; } } ``` ### Csharp ```csharp public class Solution { public int str_str(string haystack, string needle) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int str_str(string haystack, string needle) { } }; ``` ### C ```c int str_str(char* haystack, char* needle) { } ``` ### Ruby ```ruby def str_str(haystack, needle) end ``` ### Perl ```perl sub str_str { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def str_str(haystack: String, needle: String): Int = { } } ``` ### Haskell ```haskell str_str :: ... -> ... str_str args = undefined ``` ### Clojure ```clojure (defn str_str [haystack needle] ) ``` ### Scheme ```scheme (define (str_str haystack needle) ) ``` ## Examples ### Example 1 **Input:** ``` haystack = "hello" needle = "ll" ``` **Output:** ``` 2 ``` **Explanation:** "ll" first appears at index 2. ### Example 2 **Input:** ``` haystack = "aaaaa" needle = "bba" ``` **Output:** ``` -1 ``` **Explanation:** "bba" is not in "aaaaa". ### Example 3 **Input:** ``` haystack = "sadbutsad" needle = "sad" ``` **Output:** ``` 0 ``` **Explanation:** "sad" first appears at index 0. ### Example 4 **Input:** ``` haystack = "hello" needle = "" ``` **Output:** ``` 0 ``` **Explanation:** Empty needle returns 0. ## Hints 1. A brute force approach checks each starting position in haystack, taking O(N × M). 2. For each position, compare characters until mismatch or full match. 3. Advanced algorithms like KMP or Rabin-Karp achieve O(N + M).