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

Given a big string (the haystack) and a small one (the needle), return the index of the first place the needle appears inside the haystack as a contiguous block — same letters, adjacent, in order — or -1 if it never appears. Two words in that sentence carry weight. "Contiguous" separates this from a subsequence search like Is Subsequence, where gaps were allowed; here the needle's characters must sit shoulder to shoulder. And "first" means the smallest starting index, so we search left to right and stop the instant we succeed.

The needle, if it appears at all, must start somewhere — and it cannot start so late that it hangs off the end of the haystack. So the only candidate starting positions run from 0 up to len(haystack) - len(needle). Walk those positions left to right; at each one, line the needle up against that slice of the haystack and compare character by character. The first slice that matches, return its index; if none do, return -1.

h_len, n_len = len(haystack), len(needle)
for i in range(h_len - n_len + 1):         # every spot the needle could fit
    if haystack[i : i + n_len] == needle:  # compare the aligned block
        return i
return -1

Now count the work. There are about H - N + 1 starting positions, and confirming a match at each compares up to N characters. In friendly input the first mismatch at each spot ends the comparison early, so it feels fast. Adversarial input erases that: haystack "aaaa…a" (H copies of 'a') with needle "aaa…ab" (N-1 a's then a b). At every starting position the first N-1 characters match and only the last one fails — so every spot pays nearly the full N comparisons, and the total climbs to about H × N. That worst case, O(H × N), is worth seeing exactly where it comes from.

Look at what that pathological run does. At position 0 it compares N-1 a's, confirms they match, hits the final mismatch — and then slides forward by exactly one and re-compares almost the same a's all over again. Every restart throws away everything the previous comparison established about characters it already read. A person searching would never do this: having just read a long run of a's, you would not re-read it from scratch one step over. The waste is re-scanning haystack characters we have already looked at.

The Knuth-Morris-Pratt algorithm removes that waste, and its key realization is that the needle itself can tell you, in advance, how far it is safe to jump after a mismatch. Suppose we have matched some prefix of the needle and then a character fails. Those matched characters are known — they are literally the start of the needle. If that matched prefix contains a smaller piece that is both its own prefix and its suffix (in "ababc", after matching "abab" the piece "ab" is such an overlap), then that overlap is already correctly aligned at the next position, so we resume comparing from there instead of restarting — and the haystack pointer never moves backward. Precomputing those safe-jump distances from the needle alone is O(N); the haystack scan is then O(H) because each haystack character is examined a constant number of times. Total: O(H + N). Building the jump table in full is a study in itself; the load-bearing idea to carry away is that the needle's own internal repetition is what lets the search avoid re-reading the haystack.

For this problem's limits (strings up to 10⁴), the plain sliding compare is entirely acceptable and is the expected answer — its worst case is rare and the code is short and obviously correct. Reach for KMP only when the input can be adversarial or huge, or when the interviewer explicitly asks for linear time. The broader reflex is the durable part: whenever a brute-force scan keeps re-reading characters it has already seen after a partial success, ask what structure in the data (here, the needle's repeated prefixes) would let you skip the re-read. That one question is the seed of KMP, the Z-algorithm, and Rabin-Karp alike. Note too the sharp contrast with Is Subsequence: there the needle could spread out with gaps, so a single greedy forward scan sufficed; here the demand for a contiguous block is exactly what forces the backtracking that KMP works to eliminate.