Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2:
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
Constraints:
1 <= haystack.length, needle.length <= 104
haystack and needle consist of only lowercase English characters.
Solutions
Solution 1: Traversal
Thinking
The first idea is to try every start \(i\) in \(\textit{haystack}\) and test whether the length-\(m\) slice equals \(\textit{needle}\). With \(n,m \le 10^4\), the worst case \(O((n-m)m)\) is about \(10^8\) and usually passes.
The bottleneck is paying \(m\) character comparisons at many near-matches. Smarter matchers amortize toward linear time, but this size does not force them yet.
We only need the first hit; a mismatch just moves on to the next \(i\).
So scan \(i\) from \(0\) to \(n-m\), return \(i\) on equality, else \(-1\). Extra space is \(O(1)\).
We compare the string \(\textit{needle}\) with each character of the string \(\textit{haystack}\) as the starting point. If we find a matching index, we return it directly.
Assuming the length of the string \(\textit{haystack}\) is \(n\) and the length of the string \(\textit{needle}\) is \(m\), the time complexity is \(O((n-m)m)\), and the space complexity is \(O(1)\).
Solution 1 may compare all \(m\) characters at every start, approaching \(O(nm)\). We want the next window to reuse work from the last one.
A fixed-length substring can be rolling-hashed: add the incoming character, drop the outgoing one, update in \(O(1)\). When the window hash equals \(\textit{needle}\)'s hash, compare the raw strings to rule out a collision.
One scan of \(\textit{haystack}\) then costs expected \(O(n+m)\).
The Rabin-Karp algorithm essentially uses a sliding window combined with a hash function to compare the hashes of fixed-length strings, which can reduce the time complexity of comparing whether two strings are the same to \(O(1)\).
Assuming the length of the string \(\textit{haystack}\) is \(n\) and the length of the string \(\textit{needle}\) is \(m\), the time complexity is \(O(n+m)\), and the space complexity is \(O(1)\).
Solution 2 makes a window comparison expected \(O(1)\), but it still hashes modulo a prime and must verify the raw strings on a collision. We want a worst-case linear scan without hashing.
After a mismatch we need not rewind \(\textit{haystack}\) to the start of the window. The prefix function of \(\textit{needle}\) stores the longest proper border of the matched prefix, so we know where in the pattern to resume.
Build \(\textit{next}\) for \(\textit{needle}\), then scan \(\textit{haystack}\) once, falling back only along \(\textit{next}\). Time \(O(n+m)\) and extra space \(O(m)\).
Compute the prefix function \(\textit{next}\) of \(\textit{needle}\), where \(\textit{next}[i]\) is the longest proper border of \(\textit{needle}[0..i]\). Scan \(\textit{haystack}\): equal characters grow the match length, and a mismatch jumps it to \(\textit{next}[j-1]\). When the match length reaches \(m\), return the start index \(i-m+1\).
The time complexity is \(O(n+m)\), and the space complexity is \(O(m)\), where \(n\) and \(m\) are the lengths of \(\textit{haystack}\) and \(\textit{needle}\).