Find the Index of the First Occurrence in a String (LeetCode 28)
You will see how the KMP prefix function finds a word in a text without ever reading a character of the text twice.
You get two strings, a text haystack and a word needle. Look for the places where needle appears in haystack as a block of consecutive characters, and return the index in haystack where the leftmost of them begins.
If needle appears nowhere in haystack, return -1.
Worked Examples
haystack = "sadbutsad", needle = "sad"0haystack = "leetcode", needle = "leeto"-1⚖️Formal Constraints & Bounds
1 <= haystack.length, needle.length <= 104haystackandneedleconsist of only lowercase English characters.
Why It Works & Core Invariant
After a mismatch, the characters just matched are a prefix of needle you already know, so the next place a match could start is set by needle alone: lps records, for every prefix, its longest border, and the search falls back to it instead of re-reading haystack.
Real-World Scenario & Production Applications
Searching a log stream for an error signature, a packet stream for an attack signature, or a DNA read for a marker sequence: the text arrives once and is long, so a search that backs up and re-reads it after every near-miss wastes work, or can't back up at all on a stream. KMP reads each character of the text exactly once.
Step-by-Step Execution Trace Table
The debugger's first preset, the trap case haystack = "abababc", needle = "ababc" (lps = [0, 0, 1, 2, 0]):
i | ch | k before | What the code does | k after |
|---|---|---|---|---|
| 0 | a | 0 | ch == needle[0]: extend | 1 |
| 1 | b | 1 | ch == needle[1]: extend | 2 |
| 2 | a | 2 | ch == needle[2]: extend | 3 |
| 3 | b | 3 | ch == needle[3]: extend | 4 |
| 4 | a | 4 | a != needle[4] (c): k = lps[3] = 2, the border "ab" is kept; then a == needle[2]: extend | 3 |
| 5 | b | 3 | ch == needle[3]: extend | 4 |
| 6 | c | 4 | ch == needle[4]: extend, k == m | 5 |
return 6 - 5 + 1 = 2. Resetting k to 0 at i = 4 would have lost the match and returned -1. |
| 1 | After a mismatch, the letters you just matched are a prefix of `needle`, so you already know them: the next possible match is set by `needle` alone, not by re-reading `haystack`. |
| 2 | Keep this true: after reading `haystack[i]`, `k` is the length of the longest prefix of `needle` that ends at `i`. `lps[j]` is the longest proper prefix of `needle[:j + 1]` that is also its suffix. |
| 3 | The shape: two loops of the same form, first one over `needle` from index 1 that fills `lps`, then one over `haystack`. Inside each, shrink `k` while the next letter doesn't fit, then grow it on a match; the second loop stops as soon as all of `needle` is matched. |
| 4 | The trap: on a mismatch set `k = lps[k - 1]`, never `k = 0`. On `"abababc"` with `needle = "ababc"` the reset loses the border `"ab"` and the only match, at index `2`. |
Target: Find the Index of the First Occurrence in a String (LeetCode 28). `lps[i]` is the longest proper prefix of `needle[:i + 1]` that is also its suffix; it depends on `needle` only.
Intervals sorted by start coordinate; monotonic stack preserves strictly increasing or decreasing element values.
Sweep: if curr.start <= prev.end: merge; Stack: while stack and nums[i] >= stack[-1]: stack.pop().
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The simple search tries every start in haystack and compares needle letter by letter, so after a near-miss it moves one step right and re-reads text it has already seen. That is up to N · M comparisons. KMP never re-reads: when a mismatch comes after k matched letters, those k letters are needle[:k], which you already know. The longest proper prefix of needle[:k] that is also its suffix, its longest border, is the most you can keep, because the next possible match must start at a suffix of what was read that is also a prefix of needle. lps[k - 1] stores that length, computed once from needle alone, so the search sets k = lps[k - 1] and tries the same text letter again.
🎼 The Analogy: Joining a Chant Halfway
You are listening for a chant, "ba-ba-ba-da", in a crowd. You hear "ba-ba-ba-ba" and the last syllable is wrong. You don't rewind the crowd and start listening from scratch: the last "ba-ba" you heard is already the start of the chant, so you carry on as if you had heard two syllables. Knowing, for every point in the chant, how much of it you may keep after a wrong syllable is exactly the lps table.
🪄 The Mathematical Harmony / Magic Trick
while k > 0 and ch != needle[k]: k = lps[k - 1]if ch == needle[k]: k += 1if k == m: return i - m + 1 k is how much of needle ends at i. A mismatch shrinks k to the next shorter border, lps[k - 1], again and again until the letter fits or k is 0; a match grows it by one. Each letter of haystack raises k at most once and every fall back lowers it, so all the fall backs together cost at most N: the search is linear. The trap is resetting k = 0 on a mismatch: on "abababc" with needle = "ababc" it throws away the border "ab" at i = 4, which is where the only match begins.
💡 Summary
Build lps for needle with the same fall-back loop, then walk haystack once: fall back with k = lps[k - 1] while the letter doesn't fit, extend on a match, and return i - m + 1 when k == m. time, space for lps.
Resetting on a mismatch (the trap):
k = 0throws away the border of what was just matched. Onhaystack = "abababc",needle = "ababc"the only match starts inside the failed attempt at index 0, so the reset returns-1instead of2; fall back withk = lps[k - 1].ifinstead ofwhile: one letter may need several fall backs. Onhaystack = "aabaa",needle = "aaa"a singleifleavesk = 1at theband reports a match at index2that isn't there; the answer is-1.lps[k]instead oflps[k - 1]: afterkmatched letters, the border you need is that ofneedle[:k], stored atlps[k - 1];lps[k]belongs to a prefix one letter longer.Returning the end: the match ends at
i, so it starts ati - m + 1.Trying every start: correct, but it re-reads the text after every near-miss: about
2.5 * 107letter comparisons on"a" * 104withneedle = "a" * 4999 + "b".
4-Phase Thought Process Model
You will see how a senior engineer spots a pattern search and defends the KMP fall back out loud.
Pattern Recognition Signals
The 10-second spot
Find needle in haystack "as a block of consecutive characters" and return "the leftmost of them": an exact pattern search in a text that can be long. Trying every start re-reads the text after every near-miss; KMP reads it once.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After reading haystack[i], k is the length of the longest prefix of needle that ends at i. On a mismatch k = lps[k - 1] until ch == needle[k] or k == 0; on a match k += 1; at k == m the answer is i - m + 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Fall back to
k = lps[k - 1], notk = 0: onhaystack = "abababc",needle = "ababc"the reset throws away the border"ab"ati = 4, where the only match begins, and returns-1instead of2.while, notif: one letter may need several fall backs. Onhaystack = "aabaa",needle = "aaa"a singleifleavesk = 1at theb, then counts thebas nothing and reports a match at2that isn't there (the answer is-1).Use
lps[k - 1], the border of thekletters matched, notlps[k]:lps[k]describes a prefix one letter longer than what was read.Return the start,
i - m + 1, noti: the match ends ati.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use KMP. The naive search tries every start and re-reads the text after each near-miss, which is up to N times M comparisons. KMP never re-reads. First I build a table from the needle alone: for each prefix, the length of its longest proper prefix that is also a suffix. Then I scan the text once, keeping k, how much of the needle ends at the current letter. On a match I extend k; on a mismatch I don't go back in the text, I fall back to the table value for the k letters I just matched, because that border is the longest part of what I read that can still start a match, and I repeat while the letter doesn't fit. The trap is resetting k to zero, which loses matches that start inside a failed attempt. Each letter raises k at most once, so the scan is linear: O(N plus M) time and O(M) space.
So: lps from the pattern alone, one forward pass over the text, and k = lps[k - 1] on every mismatch.
Complexity & Mathematical Proof
O(N + M)
Look at the second loop: for i, ch in enumerate(haystack) runs N times, and each round does k += 1 at most once. The inner while looks quadratic, but every k = lps[k - 1] makes k strictly smaller, because lps[k - 1] < k, and k never goes below 0. k rises at most N times in all, so it can fall at most N times in all: the whole loop is O(N). The first loop is the same argument on needle against itself, O(M). Total: O(N + M).
O(M)
lps holds M integers; k, i and ch are single values. Space: O(M), and the answer is one integer.
T(N, M) = O(M) to build lps + O(N) to scan = O(N + M)
Look at the second loop: for i, ch in enumerate(haystack) runs N times, and each round does k += 1 at most once. The inner while looks quadratic, but every k = lps[k - 1] makes k strictly smaller, because lps[k - 1] < k, and k never goes below 0. k rises at most N times in all, so it can fall at most N times in all: the whole loop is O(N). The first loop is the same argument on needle against itself, O(M). Total: O(N + M).
Derivation Progression
O(M)
for i in range(1, m): k += 1 at most once per round, and each k = lps[k - 1] lowers k, so the fall backs add up to at most M.
O(N)
for i, ch in enumerate(haystack): k rises at most once per letter, so it falls at most N times in all.
O(N + M)
Two linear passes; no letter of haystack is read twice.
Variable Definitions
Length of haystack
Length of needle, m in the code
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(M): lps
O(1): one integer
Boundary Best / Worst Cases
plus a short scan: a match at index 0 returns after M letters of haystack
: no match, or a match at the very end
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "as a block of consecutive characters", "the leftmost of them". Find a word in a long text, the text read once: KMP, a border table of the word and a scan that never backs up.
. Trying every start is , about letter comparisons when needle is half of haystack; KMP is , and a rolling hash (Rabin-Karp) is expected.
Fall back with k = lps[k - 1], never k = 0. On a stream, KMP needs only lps and k (O(M) memory) and never buffers the text, which a naive search can't do. For many patterns at once, the same border idea becomes the Aho-Corasick automaton; for one pattern, str.find in CPython is already a linear-time search in C.
Core Algorithmic State Invariants
After `k` matched letters, `needle[:k]` is known, so `k = lps[k - 1]` keeps its longest border: the longest part of what was read that can still start a match. Resetting to `0` would miss a match that begins inside a failed attempt.
`lps` is built from `needle` alone, with the same `while k > 0 and needle[i] != needle[k]: k = lps[k - 1]` loop the search uses: building it is searching `needle` in itself.
`i` only moves forward and each letter raises `k` at most once, so all the fall backs together are at most `N`: O(N + M) time, O(M) space for `lps`.
Find the Index of the First Occurrence in a String (LeetCode 28)
You will see how the KMP prefix function finds a word in a text without ever reading a character of the text twice.
You get two strings, a text haystack and a word needle. Look for the places where needle appears in haystack as a block of consecutive characters, and return the index in haystack where the leftmost of them begins.
If needle appears nowhere in haystack, return -1.
Worked Examples
haystack = "sadbutsad", needle = "sad"0haystack = "leetcode", needle = "leeto"-1⚖️Formal Constraints & Bounds
1 <= haystack.length, needle.length <= 104haystackandneedleconsist of only lowercase English characters.
Why It Works & Core Invariant
After a mismatch, the characters just matched are a prefix of needle you already know, so the next place a match could start is set by needle alone: lps records, for every prefix, its longest border, and the search falls back to it instead of re-reading haystack.
Real-World Scenario & Production Applications
Searching a log stream for an error signature, a packet stream for an attack signature, or a DNA read for a marker sequence: the text arrives once and is long, so a search that backs up and re-reads it after every near-miss wastes work, or can't back up at all on a stream. KMP reads each character of the text exactly once.
Step-by-Step Execution Trace Table
The debugger's first preset, the trap case haystack = "abababc", needle = "ababc" (lps = [0, 0, 1, 2, 0]):
i | ch | k before | What the code does | k after |
|---|---|---|---|---|
| 0 | a | 0 | ch == needle[0]: extend | 1 |
| 1 | b | 1 | ch == needle[1]: extend | 2 |
| 2 | a | 2 | ch == needle[2]: extend | 3 |
| 3 | b | 3 | ch == needle[3]: extend | 4 |
| 4 | a | 4 | a != needle[4] (c): k = lps[3] = 2, the border "ab" is kept; then a == needle[2]: extend | 3 |
| 5 | b | 3 | ch == needle[3]: extend | 4 |
| 6 | c | 4 | ch == needle[4]: extend, k == m | 5 |
return 6 - 5 + 1 = 2. Resetting k to 0 at i = 4 would have lost the match and returned -1. |
| 1 | After a mismatch, the letters you just matched are a prefix of `needle`, so you already know them: the next possible match is set by `needle` alone, not by re-reading `haystack`. |
| 2 | Keep this true: after reading `haystack[i]`, `k` is the length of the longest prefix of `needle` that ends at `i`. `lps[j]` is the longest proper prefix of `needle[:j + 1]` that is also its suffix. |
| 3 | The shape: two loops of the same form, first one over `needle` from index 1 that fills `lps`, then one over `haystack`. Inside each, shrink `k` while the next letter doesn't fit, then grow it on a match; the second loop stops as soon as all of `needle` is matched. |
| 4 | The trap: on a mismatch set `k = lps[k - 1]`, never `k = 0`. On `"abababc"` with `needle = "ababc"` the reset loses the border `"ab"` and the only match, at index `2`. |
Target: Find the Index of the First Occurrence in a String (LeetCode 28). `lps[i]` is the longest proper prefix of `needle[:i + 1]` that is also its suffix; it depends on `needle` only.
Intervals sorted by start coordinate; monotonic stack preserves strictly increasing or decreasing element values.
Sweep: if curr.start <= prev.end: merge; Stack: while stack and nums[i] >= stack[-1]: stack.pop().
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The simple search tries every start in haystack and compares needle letter by letter, so after a near-miss it moves one step right and re-reads text it has already seen. That is up to N · M comparisons. KMP never re-reads: when a mismatch comes after k matched letters, those k letters are needle[:k], which you already know. The longest proper prefix of needle[:k] that is also its suffix, its longest border, is the most you can keep, because the next possible match must start at a suffix of what was read that is also a prefix of needle. lps[k - 1] stores that length, computed once from needle alone, so the search sets k = lps[k - 1] and tries the same text letter again.
🎼 The Analogy: Joining a Chant Halfway
You are listening for a chant, "ba-ba-ba-da", in a crowd. You hear "ba-ba-ba-ba" and the last syllable is wrong. You don't rewind the crowd and start listening from scratch: the last "ba-ba" you heard is already the start of the chant, so you carry on as if you had heard two syllables. Knowing, for every point in the chant, how much of it you may keep after a wrong syllable is exactly the lps table.
🪄 The Mathematical Harmony / Magic Trick
while k > 0 and ch != needle[k]: k = lps[k - 1]if ch == needle[k]: k += 1if k == m: return i - m + 1 k is how much of needle ends at i. A mismatch shrinks k to the next shorter border, lps[k - 1], again and again until the letter fits or k is 0; a match grows it by one. Each letter of haystack raises k at most once and every fall back lowers it, so all the fall backs together cost at most N: the search is linear. The trap is resetting k = 0 on a mismatch: on "abababc" with needle = "ababc" it throws away the border "ab" at i = 4, which is where the only match begins.
💡 Summary
Build lps for needle with the same fall-back loop, then walk haystack once: fall back with k = lps[k - 1] while the letter doesn't fit, extend on a match, and return i - m + 1 when k == m. time, space for lps.
Resetting on a mismatch (the trap):
k = 0throws away the border of what was just matched. Onhaystack = "abababc",needle = "ababc"the only match starts inside the failed attempt at index 0, so the reset returns-1instead of2; fall back withk = lps[k - 1].ifinstead ofwhile: one letter may need several fall backs. Onhaystack = "aabaa",needle = "aaa"a singleifleavesk = 1at theband reports a match at index2that isn't there; the answer is-1.lps[k]instead oflps[k - 1]: afterkmatched letters, the border you need is that ofneedle[:k], stored atlps[k - 1];lps[k]belongs to a prefix one letter longer.Returning the end: the match ends at
i, so it starts ati - m + 1.Trying every start: correct, but it re-reads the text after every near-miss: about
2.5 * 107letter comparisons on"a" * 104withneedle = "a" * 4999 + "b".
4-Phase Thought Process Model
You will see how a senior engineer spots a pattern search and defends the KMP fall back out loud.
Pattern Recognition Signals
The 10-second spot
Find needle in haystack "as a block of consecutive characters" and return "the leftmost of them": an exact pattern search in a text that can be long. Trying every start re-reads the text after every near-miss; KMP reads it once.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After reading haystack[i], k is the length of the longest prefix of needle that ends at i. On a mismatch k = lps[k - 1] until ch == needle[k] or k == 0; on a match k += 1; at k == m the answer is i - m + 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Fall back to
k = lps[k - 1], notk = 0: onhaystack = "abababc",needle = "ababc"the reset throws away the border"ab"ati = 4, where the only match begins, and returns-1instead of2.while, notif: one letter may need several fall backs. Onhaystack = "aabaa",needle = "aaa"a singleifleavesk = 1at theb, then counts thebas nothing and reports a match at2that isn't there (the answer is-1).Use
lps[k - 1], the border of thekletters matched, notlps[k]:lps[k]describes a prefix one letter longer than what was read.Return the start,
i - m + 1, noti: the match ends ati.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use KMP. The naive search tries every start and re-reads the text after each near-miss, which is up to N times M comparisons. KMP never re-reads. First I build a table from the needle alone: for each prefix, the length of its longest proper prefix that is also a suffix. Then I scan the text once, keeping k, how much of the needle ends at the current letter. On a match I extend k; on a mismatch I don't go back in the text, I fall back to the table value for the k letters I just matched, because that border is the longest part of what I read that can still start a match, and I repeat while the letter doesn't fit. The trap is resetting k to zero, which loses matches that start inside a failed attempt. Each letter raises k at most once, so the scan is linear: O(N plus M) time and O(M) space.
So: lps from the pattern alone, one forward pass over the text, and k = lps[k - 1] on every mismatch.
Complexity & Mathematical Proof
O(N + M)
Look at the second loop: for i, ch in enumerate(haystack) runs N times, and each round does k += 1 at most once. The inner while looks quadratic, but every k = lps[k - 1] makes k strictly smaller, because lps[k - 1] < k, and k never goes below 0. k rises at most N times in all, so it can fall at most N times in all: the whole loop is O(N). The first loop is the same argument on needle against itself, O(M). Total: O(N + M).
O(M)
lps holds M integers; k, i and ch are single values. Space: O(M), and the answer is one integer.
T(N, M) = O(M) to build lps + O(N) to scan = O(N + M)
Look at the second loop: for i, ch in enumerate(haystack) runs N times, and each round does k += 1 at most once. The inner while looks quadratic, but every k = lps[k - 1] makes k strictly smaller, because lps[k - 1] < k, and k never goes below 0. k rises at most N times in all, so it can fall at most N times in all: the whole loop is O(N). The first loop is the same argument on needle against itself, O(M). Total: O(N + M).
Derivation Progression
O(M)
for i in range(1, m): k += 1 at most once per round, and each k = lps[k - 1] lowers k, so the fall backs add up to at most M.
O(N)
for i, ch in enumerate(haystack): k rises at most once per letter, so it falls at most N times in all.
O(N + M)
Two linear passes; no letter of haystack is read twice.
Variable Definitions
Length of haystack
Length of needle, m in the code
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(M): lps
O(1): one integer
Boundary Best / Worst Cases
plus a short scan: a match at index 0 returns after M letters of haystack
: no match, or a match at the very end
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "as a block of consecutive characters", "the leftmost of them". Find a word in a long text, the text read once: KMP, a border table of the word and a scan that never backs up.
. Trying every start is , about letter comparisons when needle is half of haystack; KMP is , and a rolling hash (Rabin-Karp) is expected.
Fall back with k = lps[k - 1], never k = 0. On a stream, KMP needs only lps and k (O(M) memory) and never buffers the text, which a naive search can't do. For many patterns at once, the same border idea becomes the Aho-Corasick automaton; for one pattern, str.find in CPython is already a linear-time search in C.
Core Algorithmic State Invariants
After `k` matched letters, `needle[:k]` is known, so `k = lps[k - 1]` keeps its longest border: the longest part of what was read that can still start a match. Resetting to `0` would miss a match that begins inside a failed attempt.
`lps` is built from `needle` alone, with the same `while k > 0 and needle[i] != needle[k]: k = lps[k - 1]` loop the search uses: building it is searching `needle` in itself.
`i` only moves forward and each letter raises `k` at most once, so all the fall backs together are at most `N`: O(N + M) time, O(M) space for `lps`.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| The border table of the pattern | lps = [0] * m | `lps[i]` is the longest proper prefix of `needle[:i + 1]` that is also its suffix; it depends on `needle` only. |
| Build it with the same fall-back loop | while k > 0 and needle[i] != needle[k]:
k = lps[k - 1] | Building `lps` is the search run on `needle` against itself. |
| Read the text once | for i, ch in enumerate(haystack): | `i` only moves forward; nothing in `haystack` is read twice. |
| On a mismatch, keep the longest border | while k > 0 and ch != needle[k]:
k = lps[k - 1] | The trap: `k = lps[k - 1]`, not `k = 0`, so a match that starts inside a failed attempt is not lost. |
| On a match, extend | if ch == needle[k]:
k += 1 | `k` counts the letters of `needle` that end at `i`. |
| The whole pattern has matched | if k == m:
return i - m + 1 | The match ends at `i`, so it starts `m - 1` letters earlier. |