Finding the First Occurrence of a Substring

This challenge focuses on a fundamental string manipulation task: locating the first instance of a substring within a larger string. This is a common operation in text processing, search algorithms, and data analysis, and understanding how to efficiently implement it is crucial for any programmer. Your task is to develop a solution that accurately identifies the starting index of the first occurrence of a given substring.

Problem Description

You are tasked with creating a function (or algorithm) that takes two strings as input: a larger string (the "haystack") and a smaller string (the "needle"). The function should return the index of the first occurrence of the "needle" within the "haystack". If the "needle" is not found within the "haystack", the function should return -1.

Key Requirements:

• Case Sensitivity: The search should be case-sensitive. "hello" is different from "Hello".
• Index Origin: The index should be zero-based (the first character of the haystack is at index 0).
• Empty Needle: If the "needle" is an empty string, the function should return 0. This is because an empty string can be considered to exist at the beginning of any string.
• Empty Haystack: If the "haystack" is empty and the "needle" is not empty, the function should return -1.

Expected Behavior:

The function should iterate through the "haystack" and compare substrings of the same length as the "needle" to the "needle". When a match is found, the function should immediately return the starting index of that match. If no match is found after examining the entire "haystack", the function should return -1.

Edge Cases to Consider:

• Empty strings for both "haystack" and "needle".
• "needle" longer than "haystack".
• "needle" appearing multiple times in "haystack" – only the first occurrence matters.
• "needle" consisting of special characters.

Examples

Example 1:

Input: haystack = "hello world", needle = "world"
Output: 6
Explanation: The substring "world" starts at index 6 in "hello world".

Example 2:

Input: haystack = "hello world", needle = "foo"
Output: -1
Explanation: The substring "foo" is not found in "hello world".

Example 3:

Input: haystack = "aaaaa", needle = "aa"
Output: 0
Explanation: The substring "aa" starts at index 0 in "aaaaa".

Example 4:

Input: haystack = "hello", needle = ""
Output: 0
Explanation: An empty string is considered to be present at the beginning of any string.

Example 5:

Input: haystack = "", needle = "hello"
Output: -1
Explanation: The needle "hello" cannot be found in an empty haystack.

Constraints

• The length of the "haystack" string will be between 0 and 1000 characters (inclusive).
• The length of the "needle" string will be between 0 and 100 characters (inclusive).
• Both strings will consist of ASCII characters.
• The solution should aim for a time complexity of O(m*n), where n is the length of the haystack and m is the length of the needle. While more efficient algorithms exist, this is a reasonable target for this challenge.

Notes

Consider using a sliding window approach to compare substrings. Think about how to efficiently compare the "needle" to portions of the "haystack" without unnecessary repetition. Remember to handle the edge cases carefully to ensure your solution is robust. The goal is to find the first occurrence, so stop searching as soon as a match is found.