Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Find the Index of the First Occurrence in a String

Problem (restated)

Return the first index where needle occurs in haystack, or -1 if it does not. Empty needle → 0.

Intuition

Naive scan is O(n·m). KMP precomputes the LPS array of the needle so a mismatch jumps to the longest proper prefix that is still a suffix, never rewinding the text.

Approaches

KMP

Unverified

Time O(n+m)Space O(m)

Idea. Build lps for the needle. Scan haystack with pointer j into the needle; on mismatch set j = lps[j-1]. When j == m, return i - m + 1.

Walkthrough. haystack sadbutsad, needle sad → 0. leetcode / leeto → -1.

Trade-offs. The template. indexOf is fine in an interview if they allow library search; KMP is the linear algorithm they want if they ask “without built-ins, O(n+m).”

Solution

function buildLps(pattern: string): number[] {
  const lps = new Array<number>(pattern.length).fill(0);
  let length = 0;
  for (let i = 1; i < pattern.length; i++) {
    while (length > 0 && pattern[i] !== pattern[length]) length = lps[length - 1]!;
    if (pattern[i] === pattern[length]) length++;
    lps[i] = length;
  }
  return lps;
}

export function strStr(haystack: string, needle: string): number {
  if (!needle) return 0;
  const lps = buildLps(needle);
  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 === needle.length) return i - j + 1;
  }
  return -1;
}

function buildLps(pattern: string): number[] {
  const lps = new Array<number>(pattern.length).fill(0);
  let length = 0;
  for (let i = 1; i < pattern.length; i++) {
    while (length > 0 && pattern[i] !== pattern[length]) length = lps[length - 1]!;
    if (pattern[i] === pattern[length]) length++;
    lps[i] = length;
  }
  return lps;
}

export function strStr(haystack: string, needle: string): number {
  if (!needle) return 0;
  const lps = buildLps(needle);
  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 === needle.length) return i - j + 1;
  }
  return -1;
}

Template connection

KMP exact match. LC 1392 is LPS of the string itself; LC 214 is LPS of s + # + reverse(s).

Reflection

lps[i] is the longest proper prefix that is also a suffix. On a mismatch, rewind the pattern by lps, and do not rewind the text.
An empty pattern answers 0. A pattern longer than the text answers −1. A match at the start answers 0.
The naive shift is O(n * m). KMP scans the text once, after the failure table is built.