Find the Index of the First Occurrence in a String

Problem

Given two strings haystack and needle, return the index of the first position in haystack where needle begins as a contiguous substring. If needle never occurs in haystack, return -1.

This is the classic strStr / substring-search problem: implement it yourself rather than calling a library find.

Examples

• haystack = "sadbutsad", needle = "sad" → 0 — "sad" occurs at indices 0 and 6; the first is 0.
• haystack = "leetcode", needle = "leeto" → -1 — "leeto" never appears.
• haystack = "mississippi", needle = "issip" → 4 — the match at index 1 fails at its 5th character, but index 4 succeeds.

Constraints

• 1 <= len(haystack), len(needle) <= 10^4
• Both strings consist of lowercase English letters only.

O(n·m) sliding comparison is accepted at these bounds, but the follow-up is the linear-time classics (KMP, Rabin–Karp).

Think about it first

TL;DR

KMP prefix-function search — O(n + m) time, O(m) space (brute-force windowing passes at these bounds; Rabin–Karp is the hashing alternative).

Approach 1 — Brute force (slide and compare)

Try every starting index in haystack where the needle could fit, and compare the m-character window against needle.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        for start in range(n - m + 1):
            if haystack[start:start + m] == needle:
                return start
        return -1

Complexity: O((n - m + 1) · m) time, O(m) space per slice. At n = m = 10^4 the worst case (e.g. "aaa...a" vs "aa...ab") is ~10^8 character comparisons — right at the edge; larger inputs or slower judges kill it, which is why the linear-time classics below exist.

Approach 2 — Rabin–Karp (rolling hash)

The insight: the brute force pays O(m) to compare each window, but a window’s hash can be updated in O(1) as it slides one character right — drop the leading character’s contribution, shift, add the new character. Rabin–Karp is this classic algorithm: compare hashes first and only do the O(m) string compare on a hash hit, so expected total work is linear.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        if m > n:
            return -1
        BASE = 256
        MOD = (1 << 61) - 1  # large prime keeps collisions rare
        target = 0
        window = 0
        for k in range(m):
            target = (target * BASE + ord(needle[k])) % MOD
            window = (window * BASE + ord(haystack[k])) % MOD
        high = pow(BASE, m - 1, MOD)  # weight of the window's leading char
        for start in range(n - m + 1):
            if window == target and haystack[start:start + m] == needle:
                return start
            if start + m < n:
                window = (window - ord(haystack[start]) * high) % MOD
                window = (window * BASE + ord(haystack[start + m])) % MOD
        return -1

Walkthrough on haystack = "sadbutsad", needle = "sad" (small numbers for intuition — treat each letter as its code):

• Hash of "sad" is s·256² + a·256 + d; the first window "sad" hashes identically.
• start = 0: hashes match → verify haystack[0:3] == "sad" → true → return 0.
• Had the first window differed (say haystack "tsadbut..."), the slide would subtract t·256², multiply by 256, add the next character — O(1) per step — until the window hash hits the target at the real match.

Complexity: O(n + m) expected time (the verify step runs only on hash hits, which are rare with a 61-bit prime modulus), O(1) extra space. Worst case degrades to O(n·m) only under adversarial collisions.

Approach 3 — Knuth–Morris–Pratt (KMP)

The insight: when a mismatch happens after matching j characters of the needle, those j characters are known — so instead of restarting, consult a precomputed table of the needle’s self-overlaps. KMP builds the prefix function lps, where lps[j] is the length of the longest proper prefix of needle[:j+1] that is also its suffix; on mismatch the needle pointer falls back to lps[j-1] while the haystack pointer never moves backward, guaranteeing worst-case linear time.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        if m > n:
            return -1

        # Build the prefix table (lps = longest proper prefix == suffix).
        lps = [0] * m
        length = 0
        i = 1
        while i < m:
            if needle[i] == needle[length]:
                length += 1
                lps[i] = length
                i += 1
            elif length:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

        # Scan the haystack; j tracks how much of the needle is matched.
        i = 0
        j = 0
        while i < n:
            if haystack[i] == needle[j]:
                i += 1
                j += 1
                if j == m:
                    return i - m
            elif j:
                j = lps[j - 1]
            else:
                i += 1
        return -1

Walkthrough on haystack = "mississippi", needle = "issip":

• Prefix table for "issip": lps = [0, 0, 0, 1, 0] (the i at index 3 matches the prefix i).
• Scan: m vs i mismatch with j = 0 → advance i to 1.
• From i = 1: match i, s, s, i → j = 4. At i = 5, haystack s vs needle p mismatch → j = lps[3] = 1 (we keep credit for the trailing i already matched; i stays at 5).
• Needle position 1 (s) matches haystack s, s → j = 3; haystack i matches → j = 4; haystack p matches needle p → j = 5 = m at i = 9 → return 9 - 5 = 4.

Complexity: O(n + m) worst-case time (each pointer only moves forward, fallbacks are amortized), O(m) space for the table.

Common pitfalls

• Off-by-one in the slide range: the last viable start is n - m, so iterate over range(n - m + 1) — forgetting the + 1 misses a match that ends exactly at the string’s end.
• In KMP, falling back with j = lps[j] instead of j = lps[j - 1], or moving i backward on mismatch — both break the linear-time invariant.
• In Rabin–Karp, returning on a hash match without the verification compare — hash collisions produce false positives; and a small modulus makes them likely.
• Forgetting the m > n guard: an empty loop range handles it in Approach 1, but the hash/KMP preprocessing will misbehave without an early exit.

Pattern takeaway

Naive substring search wastes the knowledge gained before each mismatch; both classic fixes are ways of caching that knowledge — Rabin–Karp compresses a window into an O(1)-updatable hash (the same hashing reflex as the rest of this pattern), while KMP precomputes the needle’s self-overlap structure so no text character is ever re-read. When a scanning algorithm re-examines characters it has already seen, look for a summary (hash, prefix table, counter) that lets the scan move strictly forward.