Find the Index of the First Occurrence in a String

You're given two strings, haystack and needle. Return the index in haystack where the first occurrence of needle begins, or -1 if needle does not appear in haystack at all.

An occurrence means needle matches a run of consecutive characters in haystack exactly. If needle appears several times, return the smallest starting index.

The direct idea is to try every start position and compare character by character. That is fine for typical text, but it repeats work on inputs like "aaaa...ab": after matching 999 characters and failing on the last, it moves one position right and re-checks almost the same 999 characters.

KMP avoids that by precomputing, for each prefix of the needle, the length of its longest proper prefix that is also a suffix. When a mismatch happens after matching j characters, you already know the last j haystack characters equal needle[0..j), so you can fall back to that border length instead of starting over. The haystack pointer never moves backward, which makes the whole search linear.

def str_str(haystack: str, needle: str) -> int:
    m = len(needle)
    # lps[k]: longest proper prefix of needle[:k+1] that is also a suffix of it
    lps = [0] * m
    length = 0
    for k in range(1, m):
        while length and needle[k] != needle[length]:
            length = lps[length - 1]
        if needle[k] == needle[length]:
            length += 1
        lps[k] = length

    j = 0
    for i, ch in enumerate(haystack):
        while j and ch != needle[j]:
            j = lps[j - 1]
        if ch == needle[j]:
            j += 1
            if j == m:
                return i - m + 1
    return -1

function strStr(haystack, needle) {
  const m = needle.length;
  // lps[k]: longest proper prefix of needle[0..k] that is also a suffix of it
  const lps = new Array(m).fill(0);
  let length = 0;
  for (let k = 1; k < m; k++) {
    while (length > 0 && needle[k] !== needle[length]) length = lps[length - 1];
    if (needle[k] === needle[length]) length++;
    lps[k] = length;
  }

  let j = 0;
  for (let i = 0; i < haystack.length; i++) {
    while (j > 0 && haystack[i] !== needle[j]) j = lps[j - 1];
    if (haystack[i] === needle[j]) {
      j++;
      if (j === m) return i - m + 1;
    }
  }
  return -1;
}

Most interviewers are happy with the O(n · m) scan if you write it cleanly and say where its worst case comes from. Mention that built-ins like find or indexOf exist, but don't use them unless they say it's allowed.

If they push for better, explain the lps idea in words first: "on a mismatch I already know what the last j characters were, so I can reuse the longest border instead of rescanning." Then write the table builder and the scan, which share the same fallback loop.