💬 Discord
Sign In
NeetCode #121LC-28EasyArrays & Hashing
← Back to All Problems

#121 · #28 · Find the Index of the First Occurrence in a String(找出字符串中第一个匹配项的下标)

📌 Problem Statement & Constraints

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. Constraints: 1 <= haystack.length, needle.length <= 10^4. The follow-up asks for an O(n + m) algorithm.

💡 Core Algorithmic Approaches

  1. The naive scan is O(n * m) in the worst case (consider haystack = "aaaa...a", needle = "aaa...ab").
  2. KMP achieves O(n + m) by precomputing the longest proper prefix that is also a suffix (the lps array) for needle.
  3. On a mismatch, the lps array tells you how far to fall back in needle without ever moving the haystack pointer backwards.
  4. An empty needle returns 0 by convention, matching most library implementations.

💻 Benchmark Python3 Implementation

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0
        n, m = len(haystack), len(needle)
        # build the longest-proper-prefix-suffix table for needle
        lps = [0] * m
        j = 0
        for i in range(1, m):
            while j and needle[i] != needle[j]:
                j = lps[j - 1]             # fall back
            if needle[i] == needle[j]:
                j += 1
                lps[i] = j
        # scan haystack without ever rewinding
        j = 0
        for i in range(n):
            while j and haystack[i] != needle[j]:
                j = lps[j - 1]
            if haystack[i] == needle[j]:
                j += 1
                if j == m:
                    return i - m + 1       # full match
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + m) with KMP: building the table is O(m) and the scan is O(n), because the j pointer never moves backwards more than it has advanced.
💾 Space Complexity
O(m) for the lps table. A rolling-hash (Rabin-Karp) solution would be O(1) space but probabilistic.

⚠️ Interview Pitfalls & Follow-ups

  • Rewinding haystack on a mismatch: that is the naive O(n * m) algorithm. KMP's whole point is to avoid it.
  • Forgetting the j guard in the while loops: needle[j] would index out of range when j == 0.
  • Off-by-one in the match index: the answer is i - m + 1, not i - m.
  • Assuming the empty needle case cannot occur: it is a standard edge case in the API contract.