Return the index of the first occurrence of needle in haystack, or -1 if it doesn't occur. Solve it twice: once with a rolling hash and once with the prefix function.
Before you code
The simple search is accepted here, but it is O(n × m) on inputs such as a run of a's searched for aaab. What makes each of the two linear methods immune to that?
Hints
- Rabin-Karp: hash the needle and the first window, roll the window, and compare characters only when the hashes match.
- KMP: compute the prefix function of the needle, then scan the haystack, falling back through π on a mismatch instead of moving backward.
- Test mississippi with issip: the simple search backs up there, and KMP must not lose the match.
Production & complexity notes
When solving Find the first occurrence in a string on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Rolling hash and Rabin-Karp to reinforce the underlying pattern.
What it practices
Linear-time pattern search, from Rolling hash and Rabin-Karp and KMP and prefix functions.