28. Find the Index of the First Occurrence in a String
You receive two lowercase strings, haystack and needle. Return the smallest 0-based index at which needle starts inside haystack, or -1 if needle never appears.
This is the substring-search primitive behind every indexOf / find in a standard library — the goal is to build it yourself rather than call one. Watch the boundaries: the needle may be longer than the haystack, may match right at the end, or may almost-match many times before it finally fits.
Example 1:
Input: haystack = "riverbed", needle = "ver"
Output: 2
Explanation: "ver" first appears starting at index 2 of "riverbed" (ri·ver·bed).
Example 2:
Input: haystack = "banana", needle = "nab"
Output: -1
Explanation: No window of "banana" spells "nab", so the answer is -1.
Constraints:
- 1 ≤ haystack.length, needle.length ≤ 10⁴
- haystack and needle consist of lowercase English letters only.
Hints:
There are only len(haystack) - len(needle) + 1 places the needle could start. Try each one and compare character by character, stopping at the first mismatch.
The naive scan re-examines characters after a partial match. KMP avoids that: precompute, for each prefix of the needle, the longest proper prefix that is also a suffix, and use it to know where to resume after a mismatch — the haystack pointer never moves backward.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: haystack = "riverbed", needle = "ver"
Expected output: 2