Find the First Occurrence of a Substring

This challenge involves searching for a smaller string (the "needle") within a larger string (the "haystack"). Your task is to find the starting index of the very first time the needle appears in the haystack. This is a fundamental operation in string manipulation with applications in text editors, search engines, and data processing.

Problem Description

Given two strings, haystack and needle, find the index of the first occurrence of needle within haystack. If needle is not part of haystack, return -1.

Key Requirements:

• Your solution should accurately identify the first appearance of needle.
• The indexing should be zero-based, meaning the first character of haystack is at index 0.

Expected Behavior:

• If needle is found, return its starting index in haystack.
• If needle is not found, return -1.
• If needle is an empty string, return 0.

Edge Cases to Consider:

• haystack is empty.
• needle is empty.
• needle is longer than haystack.
• needle appears multiple times in haystack.

Examples

Example 1:

Input:
haystack = "sadbutsad"
needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 in "sadbutsad".

Example 2:

Input:
haystack = "leetcode"
needle = "leeto"
Output: -1
Explanation: "leeto" is not a substring of "leetcode".

Example 3:

Input:
haystack = "mississippi"
needle = "issipi"
Output: -1
Explanation: While "issi" appears multiple times, "issipi" as a whole does not appear.

Example 4:

Input:
haystack = "hello"
needle = ""
Output: 0
Explanation: An empty needle is considered to be found at the beginning of any haystack (index 0).

Constraints

• 1 <= haystack.length <= 10^4
• 1 <= needle.length <= 10^4
• haystack and needle consist of lowercase English letters.
• Your solution should aim for an efficient time complexity.

Notes

Consider how you would iterate through the haystack and compare portions of it to the needle. Think about what happens when a potential match starts but doesn't fully complete. Pseudocode might involve nested loops or a sliding window approach. Remember the edge case of an empty needle.