Implement strStr
viaLeetCode
Problem Return the index of the first occurrence of needle in haystack, or -1 if absent (empty needle → 0).
Input / Output
- Input: strings haystack, needle.
- Output: first match index or -1.
Constraints
- Lengths up to 510^4; the naive O(nm) sliding compare is acceptable; know a linear-time option.
Example
- haystack = "sadbutsad", needle = "sad" → 0.
Expected approach
- Baseline: for each window start, compare needle with early exit — O(n*m) worst case but fine in practice. Level-up answers: KMP (prefix-function automaton, O(n+m), no backtracking in haystack) or Rabin–Karp (rolling hash, O(n+m) expected). Interviewers typically accept the naive version but probe the KMP idea; know why the prefix table lets the pattern shift without rescanning the text.
asked …