Implement strStr

Implement strStr easy

Description

Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Examples

> Case 1:
    haystack = "sadbutsad",  needle = "sad"
    Output: 0
    Explanation: "sad" occurs at index 0 and index 6. First is 0.
 
> Case 2:
    haystack = "leetcode",  needle = "leeto"
    Output: -1
    Explanation: "leeto" did not occur in "leetcode".

Constraints

1 <= haystack.length, needle.length <= 10^4
haystack and needle consist of only lowercase English letters.

State design / Intuition

The naive approach slides needle across haystack and compares character-by-character at each position. This is O(nm) — acceptable for the given constraints, but a good interview response mentions KMP and explains why.

The KMP approach:

Build the failure function for needle in O(m).
Scan haystack with two pointers (one for the text, one for the pattern position), using the failure function to avoid re-scanning.
The text pointer never moves backward — O(n) total.

For this problem the naive approach passes within the constraints (n, m <= 10^4 means at most 10^8 comparisons, which is borderline). KMP is the correct answer if asked for the optimal solution.

Code

Analysis

Time: O(n + m) — O(m) to build the failure function, O(n) for the search.
Space: O(m) — the failure function array.

Same skin

Find all occurrences — modify to collect all matches: after j == m, record i - m + 1 then set j = fail[j - 1] and continue.
Longest Happy Prefix — building only the failure function, return fail[m - 1].
Shortest Palindrome — use KMP on s + '#' + reverse(s) to find the longest palindrome prefix.
Count occurrences of pattern — KMP with overlap counting via j = fail[j-1] after each match.

Overview Repeated Substring Pattern