What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Two Pointers & Sliding Window

Builds on Hash Map, which you haven’t finished yet.

P3HardMental model~6 min speedrun

Knuth-Morris-Pratt (KMP) String Matching

The problem

Find the Index of the First Occurrence in a String (LC 28)(opens leetcode.com)

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.

Example 1

Input:haystack = "sadbutsad", needle = "sad"

Output:0

The scan stops at the first full match, which starts at index 0; the second copy of "sad", at index 6, is never reached.

KMP

Spot it when: You must find an exact pattern in a long text, or a prefix of a string that comes back later in it (a border, a period, a repeated start), in linear time.

Not this one if…

The pattern may appear with its letters in any order, as in Find All Anagrams in a String (LC 438): order doesn't matter, so a window of letter counts, not a prefix of the pattern, decides a match. See Fixed Window

KMP

Python

1	def str_str(haystack: str, needle: str) -> int:
2	"""KMP: find needle in haystack without ever moving back in haystack.
3	Time: O(N + M) \| Space: O(M)
4	"""
5	m = len(needle)
6	# lps[i]: the longest proper prefix of needle[:i + 1] that is also its suffix (its longest border).
7	lps = [0] * m
8	k = 0 # Length of the prefix of needle matched so far
9
10	# 1. Build The Border Table From needle Against Itself:
11	# Building lps runs the same search on needle against itself, so a mismatch falls back to a
12	# shorter border the same way the main search below does.
13	for i in range(1, m):
14	while k > 0 and needle[i] != needle[k]:
15	k = lps[k - 1]
16	if needle[i] == needle[k]:
17	k += 1
18	lps[i] = k
19
20	# 2. Scan haystack Once, Falling Back Instead Of Restarting:
21	# On a mismatch, the k letters just matched are needle[:k], already known, so k falls back
22	# to the longest border that still fits; the match ends at i, so it starts i - m + 1 letters
23	# earlier.
24	k = 0
25	for i, ch in enumerate(haystack):
26	while k > 0 and ch != needle[k]:
27	k = lps[k - 1]
28	if ch == needle[k]:
29	k += 1
30	if k == m:
31	return i - m + 1
32	return -1

Invariant: After reading haystack[i], k is the length of the longest prefix of needle that ends at i, and lps[j] is the longest proper prefix of needle[:j + 1] that is also its suffix.

KMP never reads a character of the text twice: when a mismatch comes after k matched letters, those letters are needle[:k], which you already know, so the search keeps their longest border, k = lps[k - 1], and tries the same letter again instead of moving the start forward by one and re-reading. It is correct because a match that is still possible must begin at a suffix of what was read that is also a prefix of needle, and lps[k - 1] is the longest such part; falling back again while k > 0 and ch != needle[k] visits every shorter one in order, and lps itself is built by running the same loop on needle against itself. The trap is resetting k = 0 on a mismatch: on haystack = "abababc", needle = "ababc" it throws away the border "ab" at i = 4, where the only match begins, and returns -1 instead of 2.

See it run

KMP String Matching, step by step

i -k 0lps 0

The top row is haystack. The middle row is needle. The bottom row is lps, the longest border of each needle prefix.

i the letter being read
k the next needle letter to compare; k letters of needle are already matched
border the lps place that was just written or just read

Start: needle has 5 letters, so lps has 5 places. lps is built first, then haystack is scanned once.

haystack

needle

lps

1 / 14

Gotchas1 of 4

The trap
Gotcha 1: Resetting k = 0 on a mismatch
Mistake
```
while k > 0 and ch != needle[k]:
    k = 0
```
Fix
```
while k > 0 and ch != needle[k]:
    k = lps[k - 1]
```
What happens: After k matched letters, the text just read is needle[:k]. Its end can also be the start of needle. A match can then begin inside the failed attempt. k = 0 throws that start away, and the search can miss the match. k = lps[k - 1] keeps it.
Example: haystack = "abababc", needle = "ababc"
Mistake: returns -1Fix: returns 2
Gotcha 2: Building lps with range(m) instead of range(1, m)
Mistake
```
for i in range(m):
```
Fix
```
for i in range(1, m):
```
What happens: lps[0] must stay 0, because a single letter has no shorter border. With range(m), the loop compares needle[0] with itself and sets lps[0] = 1. A fall back from k = 1 then sets k = lps[0], which is 1 again. The while loop never ends.
Example: haystack = "ab", needle = "ac"
Mistake: the loop never endsFix: returns -1
Gotcha 3: Falling back once with if instead of while
Mistake
```
if k > 0 and ch != needle[k]:
```
Fix
```
while k > 0 and ch != needle[k]:
```
What happens: After one fall back, the letter may still not match needle[k]. The search must then fall back again, to a shorter border. With if, it falls back once and moves on. k then counts letters that were never matched.
Example: haystack = "aabaa", needle = "aaa"
Mistake: returns 2Fix: returns -1
Gotcha 4: Falling back to lps[k] instead of lps[k - 1]
Mistake
```
while k > 0 and ch != needle[k]:
    k = lps[k]
```
Fix
```
while k > 0 and ch != needle[k]:
    k = lps[k - 1]
```
What happens: After k matched letters, the text read is needle[:k]. Its border is stored at lps[k - 1], because lps[i] describes needle[:i + 1]. lps[k] describes a prefix one letter longer than what was read. In this example, k is 2 at the b, and lps[2] is also 2. k never changes, so the while loop never ends.
Example: haystack = "aabaaab", needle = "aaab"
Mistake: the loop never endsFix: returns 3

Deep Dive

A mismatch must not send the search backward

The simple search tries every start position in haystack. At each start it compares letters until one differs, then it moves the start forward by one and compares again from the first letter of needle. It reads the same letters of haystack many times. On haystack = "aaaaaaaa" and needle = "aaab" it makes 20 comparisons, and the cost grows to O(N * M) for longer inputs.

KMP (Knuth-Morris-Pratt) never moves its position in haystack backward. Suppose k letters matched and the next letter differs. The k letters just read are exactly needle[:k], and you already know them. You do not need to read them again.

A new match can still start inside those k letters. It must start at a suffix of needle[:k] that is also a prefix of needle. A part of a string that is both a prefix and a suffix of it is called a border. The longest border of needle[:k] is lps[k - 1], so the search sets k = lps[k - 1] and compares the same letter of haystack again.

If that letter still differs, the loop while k > 0 and ch != needle[k] falls back again, to the next shorter border. The loop visits every possible start in order from the longest, and it stops at the first one that fits.

Building lps with the same loop

lps[i] is the length of the longest border of needle[:i + 1] that is shorter than the whole prefix. For needle = "ababc" the table is [0, 0, 1, 2, 0]. At i = 3 the prefix "abab" has the border "ab", so lps[3] = 2.

The table is built by searching needle inside itself. The loop starts at i = 1. lps[0] stays 0, because a single letter has no shorter border. For each i, k is the length of the border of needle[:i]. If needle[i] == needle[k], the border grows by one letter and k += 1. If not, k falls back to lps[k - 1] and the same letter is compared again.

Because the build and the search are the same loop, one idea explains both. k is always the length of the longest prefix of needle that ends at the letter just read.

Find "ababc" in "abababc", traced

Take haystack = "abababc" and needle = "ababc". The build gives lps = [0, 0, 1, 2, 0]. At i = 4 the letter "c" differs from needle[2] = "a", so k falls back to lps[1] = 0, and "c" matches nothing.

The search reads "abab" and k grows to 4. At i = 4 the letter "a" differs from needle[4] = "c". The border of "abab" is "ab", so k = lps[3] = 2. The letter "a" then matches needle[2], and k = 3.

At i = 5 the letter "b" gives k = 4. At i = 6 the letter "c" gives k = 5 = m. The match ends at i = 6, so it starts at 6 - 5 + 1 = 2.

The board marks the trap at i = 4. With k = 0 instead of k = lps[3], the search forgets that "ab" is already matched. At i = 6 the letter "c" is then compared with needle[2], the match is lost, and the result is -1 instead of 2.

Why the cost is O(N + M)

In the search, each letter of haystack increases k by at most 1. Each fall back makes k smaller. So the total number of fall backs cannot be more than the total number of increases, which is at most N. The scan costs O(N).

The build follows the same argument on needle, so it costs O(M). The total time is O(N + M). The only extra memory is lps, so the space is O(M).

The same table solves other problems. lps[m - 1] is the length of the longest border of the whole string, which is the answer to Longest Happy Prefix (LC 1392). A string of length m is a repeated block when p = m - lps[m - 1] is smaller than m and divides m, as in Repeated Substring Pattern (LC 459).

60-Second Pitch

"The simple search re-reads haystack after every mismatch, which costs O(N * M). KMP never goes back. When k letters matched and the next one differs, those k letters are needle[:k], which I already know. So I keep their longest border, k = lps[k - 1], and compare the same letter again. The table lps stores the longest border of each prefix of needle. I build it with the same loop, searching needle inside itself. Then one scan of haystack with a while fall back returns i - m + 1 when k reaches m. Each letter raises k by at most one and each fall back lowers it, so the time is O(N + M) and the space is O(M). The same table gives Longest Happy Prefix as lps[m - 1]."

Common Questions

Why is the time O(N + M) and not O(N * M)?: k goes up by at most 1 for each letter of haystack, and every fall back lowers it. The number of fall backs therefore cannot exceed the number of increases. The scan makes at most about 2N steps, and the build makes at most about 2M steps.
Why lps[k - 1] and not lps[k]?: lps[i] describes needle[:i + 1]. After k matched letters, the text read is needle[:k], so its border is at index k - 1. lps[k] describes a prefix one letter longer than what was read, and the while loop can then run forever.
How do you find every occurrence, not only the first?: When k == m, record i - m + 1 and then set k = lps[m - 1] instead of returning. The next match may overlap this one. On haystack = "aaaaa" and needle = "aa" this finds the starts [0, 1, 2, 3].
How does the same table solve Longest Happy Prefix (LC 1392)?: A happy prefix is a non-empty prefix that is also a suffix and is shorter than the whole string. That is a border, so the answer is s[:lps[m - 1]]. For s = "level" the table ends in 1, and the answer is "l".
Why not use a hash of each window instead?: A rolling hash (Rabin-Karp) compares one number per window and is fast on average. Two different windows can have the same hash, so every hash match needs a letter-by-letter check. KMP has no such case, and its O(N + M) time holds for every input.

SWE Reasoning

Spot it

You must find an exact pattern in a long text in O(N + M), as in Find the Index of the First Occurrence in a String (LC 28).
The question is about a prefix of a string that comes back later in it: a border, a period or a repeated start (Longest Happy Prefix (LC 1392), Repeated Substring Pattern (LC 459), Shortest Palindrome (LC 214)).
The simple search re-reads letters after a mismatch, and the input is large enough for O(N * M) to be too slow.
Letters must match in order. If the pattern may appear with its letters in any order, this is a window of letter counts instead.

The invariant, step by step

lps is built first. lps[j] is the length of the longest border of needle[:j + 1] that is shorter than that prefix.
The search starts with k = 0. k is the number of letters of needle matched at the end of what was read.
For each letter ch of haystack, k falls back with k = lps[k - 1] while k > 0 and ch != needle[k]. Each fall back keeps the longest part that can still start a match.
If ch == needle[k], then k += 1. After this step, k is the length of the longest prefix of needle that ends at ch.
When k == m, the whole needle ends at i, so it starts at i - m + 1. If haystack ends first, the answer is -1.

Traps

Resetting k = 0 on a mismatch. The search forgets a border that was already matched. On haystack = "abababc" and needle = "ababc" it returns -1 instead of 2.
Building lps with range(m). The loop compares needle[0] with itself, sets lps[0] = 1, and a later fall back never ends.
Using if instead of while for the fall back. After one fall back the letter may still differ, so k then counts letters that were never matched.
Using lps[k] instead of lps[k - 1]. lps[i] describes needle[:i + 1], so the border of the k letters read is at lps[k - 1].

Practice

Canonical LeetCode:Find the Index of the First Occurrence in a String (LC 28)Longest Happy Prefix (LC 1392)Repeated Substring Pattern (LC 459)Shortest Palindrome (LC 214)

Theory Context•Two Pointers & Sliding Window

Builds on Hash Map, which you haven’t finished yet.

P3HardMental model~6 min speedrun

Knuth-Morris-Pratt (KMP) String Matching

The problem

Find the Index of the First Occurrence in a String (LC 28)(opens leetcode.com)

If needle appears nowhere in haystack, return -1.

Example 1

Input:haystack = "sadbutsad", needle = "sad"

Output:0

The scan stops at the first full match, which starts at index 0; the second copy of "sad", at index 6, is never reached.

KMP

Spot it when: You must find an exact pattern in a long text, or a prefix of a string that comes back later in it (a border, a period, a repeated start), in linear time.

Not this one if…

The pattern may appear with its letters in any order, as in Find All Anagrams in a String (LC 438): order doesn't matter, so a window of letter counts, not a prefix of the pattern, decides a match. See Fixed Window

KMP

Python

1	def str_str(haystack: str, needle: str) -> int:
2	"""KMP: find needle in haystack without ever moving back in haystack.
3	Time: O(N + M) \| Space: O(M)
4	"""
5	m = len(needle)
6	# lps[i]: the longest proper prefix of needle[:i + 1] that is also its suffix (its longest border).
7	lps = [0] * m
8	k = 0 # Length of the prefix of needle matched so far
9
10	# 1. Build The Border Table From needle Against Itself:
11	# Building lps runs the same search on needle against itself, so a mismatch falls back to a
12	# shorter border the same way the main search below does.
13	for i in range(1, m):
14	while k > 0 and needle[i] != needle[k]:
15	k = lps[k - 1]
16	if needle[i] == needle[k]:
17	k += 1
18	lps[i] = k
19
20	# 2. Scan haystack Once, Falling Back Instead Of Restarting:
21	# On a mismatch, the k letters just matched are needle[:k], already known, so k falls back
22	# to the longest border that still fits; the match ends at i, so it starts i - m + 1 letters
23	# earlier.
24	k = 0
25	for i, ch in enumerate(haystack):
26	while k > 0 and ch != needle[k]:
27	k = lps[k - 1]
28	if ch == needle[k]:
29	k += 1
30	if k == m:
31	return i - m + 1
32	return -1

Invariant: After reading haystack[i], k is the length of the longest prefix of needle that ends at i, and lps[j] is the longest proper prefix of needle[:j + 1] that is also its suffix.

See it run

KMP String Matching, step by step

i -k 0lps 0

The top row is haystack. The middle row is needle. The bottom row is lps, the longest border of each needle prefix.

i the letter being read
k the next needle letter to compare; k letters of needle are already matched
border the lps place that was just written or just read

Start: needle has 5 letters, so lps has 5 places. lps is built first, then haystack is scanned once.

haystack

needle

lps

1 / 14

Gotchas1 of 4

The trap
Gotcha 1: Resetting k = 0 on a mismatch
Mistake
```
while k > 0 and ch != needle[k]:
    k = 0
```
Fix
```
while k > 0 and ch != needle[k]:
    k = lps[k - 1]
```
What happens: After k matched letters, the text just read is needle[:k]. Its end can also be the start of needle. A match can then begin inside the failed attempt. k = 0 throws that start away, and the search can miss the match. k = lps[k - 1] keeps it.
Example: haystack = "abababc", needle = "ababc"
Mistake: returns -1Fix: returns 2
Gotcha 2: Building lps with range(m) instead of range(1, m)
Mistake
```
for i in range(m):
```
Fix
```
for i in range(1, m):
```
What happens: lps[0] must stay 0, because a single letter has no shorter border. With range(m), the loop compares needle[0] with itself and sets lps[0] = 1. A fall back from k = 1 then sets k = lps[0], which is 1 again. The while loop never ends.
Example: haystack = "ab", needle = "ac"
Mistake: the loop never endsFix: returns -1
Gotcha 3: Falling back once with if instead of while
Mistake
```
if k > 0 and ch != needle[k]:
```
Fix
```
while k > 0 and ch != needle[k]:
```
What happens: After one fall back, the letter may still not match needle[k]. The search must then fall back again, to a shorter border. With if, it falls back once and moves on. k then counts letters that were never matched.
Example: haystack = "aabaa", needle = "aaa"
Mistake: returns 2Fix: returns -1
Gotcha 4: Falling back to lps[k] instead of lps[k - 1]
Mistake
```
while k > 0 and ch != needle[k]:
    k = lps[k]
```
Fix
```
while k > 0 and ch != needle[k]:
    k = lps[k - 1]
```
What happens: After k matched letters, the text read is needle[:k]. Its border is stored at lps[k - 1], because lps[i] describes needle[:i + 1]. lps[k] describes a prefix one letter longer than what was read. In this example, k is 2 at the b, and lps[2] is also 2. k never changes, so the while loop never ends.
Example: haystack = "aabaaab", needle = "aaab"
Mistake: the loop never endsFix: returns 3

Deep Dive

A mismatch must not send the search backward

Building lps with the same loop

Because the build and the search are the same loop, one idea explains both. k is always the length of the longest prefix of needle that ends at the letter just read.

Find "ababc" in "abababc", traced

At i = 5 the letter "b" gives k = 4. At i = 6 the letter "c" gives k = 5 = m. The match ends at i = 6, so it starts at 6 - 5 + 1 = 2.

Why the cost is O(N + M)

The build follows the same argument on needle, so it costs O(M). The total time is O(N + M). The only extra memory is lps, so the space is O(M).

60-Second Pitch

Common Questions

Why is the time O(N + M) and not O(N * M)?: k goes up by at most 1 for each letter of haystack, and every fall back lowers it. The number of fall backs therefore cannot exceed the number of increases. The scan makes at most about 2N steps, and the build makes at most about 2M steps.
Why lps[k - 1] and not lps[k]?: lps[i] describes needle[:i + 1]. After k matched letters, the text read is needle[:k], so its border is at index k - 1. lps[k] describes a prefix one letter longer than what was read, and the while loop can then run forever.
How do you find every occurrence, not only the first?: When k == m, record i - m + 1 and then set k = lps[m - 1] instead of returning. The next match may overlap this one. On haystack = "aaaaa" and needle = "aa" this finds the starts [0, 1, 2, 3].
How does the same table solve Longest Happy Prefix (LC 1392)?: A happy prefix is a non-empty prefix that is also a suffix and is shorter than the whole string. That is a border, so the answer is s[:lps[m - 1]]. For s = "level" the table ends in 1, and the answer is "l".
Why not use a hash of each window instead?: A rolling hash (Rabin-Karp) compares one number per window and is fast on average. Two different windows can have the same hash, so every hash match needs a letter-by-letter check. KMP has no such case, and its O(N + M) time holds for every input.

SWE Reasoning

Spot it

You must find an exact pattern in a long text in O(N + M), as in Find the Index of the First Occurrence in a String (LC 28).
The question is about a prefix of a string that comes back later in it: a border, a period or a repeated start (Longest Happy Prefix (LC 1392), Repeated Substring Pattern (LC 459), Shortest Palindrome (LC 214)).
The simple search re-reads letters after a mismatch, and the input is large enough for O(N * M) to be too slow.
Letters must match in order. If the pattern may appear with its letters in any order, this is a window of letter counts instead.

The invariant, step by step

lps is built first. lps[j] is the length of the longest border of needle[:j + 1] that is shorter than that prefix.
The search starts with k = 0. k is the number of letters of needle matched at the end of what was read.
For each letter ch of haystack, k falls back with k = lps[k - 1] while k > 0 and ch != needle[k]. Each fall back keeps the longest part that can still start a match.
If ch == needle[k], then k += 1. After this step, k is the length of the longest prefix of needle that ends at ch.
When k == m, the whole needle ends at i, so it starts at i - m + 1. If haystack ends first, the answer is -1.

Traps

Resetting k = 0 on a mismatch. The search forgets a border that was already matched. On haystack = "abababc" and needle = "ababc" it returns -1 instead of 2.
Building lps with range(m). The loop compares needle[0] with itself, sets lps[0] = 1, and a later fall back never ends.
Using if instead of while for the fall back. After one fall back the letter may still differ, so k then counts letters that were never matched.
Using lps[k] instead of lps[k - 1]. lps[i] describes needle[:i + 1], so the border of the k letters read is at lps[k - 1].

Practice

Canonical LeetCode:Find the Index of the First Occurrence in a String (LC 28)Longest Happy Prefix (LC 1392)Repeated Substring Pattern (LC 459)Shortest Palindrome (LC 214)

Theory Context•Two Pointers & Sliding Window

Builds on Hash Map, which you haven’t finished yet.

P3HardMental model~6 min speedrun

Knuth-Morris-Pratt (KMP) String Matching

The problem

Find the Index of the First Occurrence in a String (LC 28)(opens leetcode.com)

If needle appears nowhere in haystack, return -1.

Example 1

Input:haystack = "sadbutsad", needle = "sad"

Output:0

The scan stops at the first full match, which starts at index 0; the second copy of "sad", at index 6, is never reached.

KMP

Spot it when: You must find an exact pattern in a long text, or a prefix of a string that comes back later in it (a border, a period, a repeated start), in linear time.

Not this one if…

The pattern may appear with its letters in any order, as in Find All Anagrams in a String (LC 438): order doesn't matter, so a window of letter counts, not a prefix of the pattern, decides a match. See Fixed Window

KMP

Python

1	def str_str(haystack: str, needle: str) -> int:
2	"""KMP: find needle in haystack without ever moving back in haystack.
3	Time: O(N + M) \| Space: O(M)
4	"""
5	m = len(needle)
6	# lps[i]: the longest proper prefix of needle[:i + 1] that is also its suffix (its longest border).
7	lps = [0] * m
8	k = 0 # Length of the prefix of needle matched so far
9
10	# 1. Build The Border Table From needle Against Itself:
11	# Building lps runs the same search on needle against itself, so a mismatch falls back to a
12	# shorter border the same way the main search below does.
13	for i in range(1, m):
14	while k > 0 and needle[i] != needle[k]:
15	k = lps[k - 1]
16	if needle[i] == needle[k]:
17	k += 1
18	lps[i] = k
19
20	# 2. Scan haystack Once, Falling Back Instead Of Restarting:
21	# On a mismatch, the k letters just matched are needle[:k], already known, so k falls back
22	# to the longest border that still fits; the match ends at i, so it starts i - m + 1 letters
23	# earlier.
24	k = 0
25	for i, ch in enumerate(haystack):
26	while k > 0 and ch != needle[k]:
27	k = lps[k - 1]
28	if ch == needle[k]:
29	k += 1
30	if k == m:
31	return i - m + 1
32	return -1

Invariant: After reading haystack[i], k is the length of the longest prefix of needle that ends at i, and lps[j] is the longest proper prefix of needle[:j + 1] that is also its suffix.

See it run

KMP String Matching, step by step

i -k 0lps 0

The top row is haystack. The middle row is needle. The bottom row is lps, the longest border of each needle prefix.

i the letter being read
k the next needle letter to compare; k letters of needle are already matched
border the lps place that was just written or just read

Start: needle has 5 letters, so lps has 5 places. lps is built first, then haystack is scanned once.

haystack

needle

lps

1 / 14

Gotchas1 of 4

The trap
Gotcha 1: Resetting k = 0 on a mismatch
Mistake
```
while k > 0 and ch != needle[k]:
    k = 0
```
Fix
```
while k > 0 and ch != needle[k]:
    k = lps[k - 1]
```
What happens: After k matched letters, the text just read is needle[:k]. Its end can also be the start of needle. A match can then begin inside the failed attempt. k = 0 throws that start away, and the search can miss the match. k = lps[k - 1] keeps it.
Example: haystack = "abababc", needle = "ababc"
Mistake: returns -1Fix: returns 2
Gotcha 2: Building lps with range(m) instead of range(1, m)
Mistake
```
for i in range(m):
```
Fix
```
for i in range(1, m):
```
What happens: lps[0] must stay 0, because a single letter has no shorter border. With range(m), the loop compares needle[0] with itself and sets lps[0] = 1. A fall back from k = 1 then sets k = lps[0], which is 1 again. The while loop never ends.
Example: haystack = "ab", needle = "ac"
Mistake: the loop never endsFix: returns -1
Gotcha 3: Falling back once with if instead of while
Mistake
```
if k > 0 and ch != needle[k]:
```
Fix
```
while k > 0 and ch != needle[k]:
```
What happens: After one fall back, the letter may still not match needle[k]. The search must then fall back again, to a shorter border. With if, it falls back once and moves on. k then counts letters that were never matched.
Example: haystack = "aabaa", needle = "aaa"
Mistake: returns 2Fix: returns -1
Gotcha 4: Falling back to lps[k] instead of lps[k - 1]
Mistake
```
while k > 0 and ch != needle[k]:
    k = lps[k]
```
Fix
```
while k > 0 and ch != needle[k]:
    k = lps[k - 1]
```
What happens: After k matched letters, the text read is needle[:k]. Its border is stored at lps[k - 1], because lps[i] describes needle[:i + 1]. lps[k] describes a prefix one letter longer than what was read. In this example, k is 2 at the b, and lps[2] is also 2. k never changes, so the while loop never ends.
Example: haystack = "aabaaab", needle = "aaab"
Mistake: the loop never endsFix: returns 3

Deep Dive

A mismatch must not send the search backward

Building lps with the same loop

Because the build and the search are the same loop, one idea explains both. k is always the length of the longest prefix of needle that ends at the letter just read.

Find "ababc" in "abababc", traced

At i = 5 the letter "b" gives k = 4. At i = 6 the letter "c" gives k = 5 = m. The match ends at i = 6, so it starts at 6 - 5 + 1 = 2.

Why the cost is O(N + M)

The build follows the same argument on needle, so it costs O(M). The total time is O(N + M). The only extra memory is lps, so the space is O(M).

60-Second Pitch

Common Questions

Why is the time O(N + M) and not O(N * M)?: k goes up by at most 1 for each letter of haystack, and every fall back lowers it. The number of fall backs therefore cannot exceed the number of increases. The scan makes at most about 2N steps, and the build makes at most about 2M steps.
Why lps[k - 1] and not lps[k]?: lps[i] describes needle[:i + 1]. After k matched letters, the text read is needle[:k], so its border is at index k - 1. lps[k] describes a prefix one letter longer than what was read, and the while loop can then run forever.
How do you find every occurrence, not only the first?: When k == m, record i - m + 1 and then set k = lps[m - 1] instead of returning. The next match may overlap this one. On haystack = "aaaaa" and needle = "aa" this finds the starts [0, 1, 2, 3].
How does the same table solve Longest Happy Prefix (LC 1392)?: A happy prefix is a non-empty prefix that is also a suffix and is shorter than the whole string. That is a border, so the answer is s[:lps[m - 1]]. For s = "level" the table ends in 1, and the answer is "l".
Why not use a hash of each window instead?: A rolling hash (Rabin-Karp) compares one number per window and is fast on average. Two different windows can have the same hash, so every hash match needs a letter-by-letter check. KMP has no such case, and its O(N + M) time holds for every input.

SWE Reasoning

Spot it

You must find an exact pattern in a long text in O(N + M), as in Find the Index of the First Occurrence in a String (LC 28).
The question is about a prefix of a string that comes back later in it: a border, a period or a repeated start (Longest Happy Prefix (LC 1392), Repeated Substring Pattern (LC 459), Shortest Palindrome (LC 214)).
The simple search re-reads letters after a mismatch, and the input is large enough for O(N * M) to be too slow.
Letters must match in order. If the pattern may appear with its letters in any order, this is a window of letter counts instead.

The invariant, step by step

lps is built first. lps[j] is the length of the longest border of needle[:j + 1] that is shorter than that prefix.
The search starts with k = 0. k is the number of letters of needle matched at the end of what was read.
For each letter ch of haystack, k falls back with k = lps[k - 1] while k > 0 and ch != needle[k]. Each fall back keeps the longest part that can still start a match.
If ch == needle[k], then k += 1. After this step, k is the length of the longest prefix of needle that ends at ch.
When k == m, the whole needle ends at i, so it starts at i - m + 1. If haystack ends first, the answer is -1.

Traps

Resetting k = 0 on a mismatch. The search forgets a border that was already matched. On haystack = "abababc" and needle = "ababc" it returns -1 instead of 2.
Building lps with range(m). The loop compares needle[0] with itself, sets lps[0] = 1, and a later fall back never ends.
Using if instead of while for the fall back. After one fall back the letter may still differ, so k then counts letters that were never matched.
Using lps[k] instead of lps[k - 1]. lps[i] describes needle[:i + 1], so the border of the k letters read is at lps[k - 1].

Practice

Canonical LeetCode:Find the Index of the First Occurrence in a String (LC 28)Longest Happy Prefix (LC 1392)Repeated Substring Pattern (LC 459)Shortest Palindrome (LC 214)

Theory Context•Two Pointers & Sliding Window

Builds on Hash Map, which you haven’t finished yet.

P3HardMental model~6 min speedrun

Knuth-Morris-Pratt (KMP) String Matching

The problem

Find the Index of the First Occurrence in a String (LC 28)(opens leetcode.com)

If needle appears nowhere in haystack, return -1.

Example 1

Input:haystack = "sadbutsad", needle = "sad"

Output:0

The scan stops at the first full match, which starts at index 0; the second copy of "sad", at index 6, is never reached.

KMP

Spot it when: You must find an exact pattern in a long text, or a prefix of a string that comes back later in it (a border, a period, a repeated start), in linear time.

Not this one if…

The pattern may appear with its letters in any order, as in Find All Anagrams in a String (LC 438): order doesn't matter, so a window of letter counts, not a prefix of the pattern, decides a match. See Fixed Window

KMP

Python

1	def str_str(haystack: str, needle: str) -> int:
2	"""KMP: find needle in haystack without ever moving back in haystack.
3	Time: O(N + M) \| Space: O(M)
4	"""
5	m = len(needle)
6	# lps[i]: the longest proper prefix of needle[:i + 1] that is also its suffix (its longest border).
7	lps = [0] * m
8	k = 0 # Length of the prefix of needle matched so far
9
10	# 1. Build The Border Table From needle Against Itself:
11	# Building lps runs the same search on needle against itself, so a mismatch falls back to a
12	# shorter border the same way the main search below does.
13	for i in range(1, m):
14	while k > 0 and needle[i] != needle[k]:
15	k = lps[k - 1]
16	if needle[i] == needle[k]:
17	k += 1
18	lps[i] = k
19
20	# 2. Scan haystack Once, Falling Back Instead Of Restarting:
21	# On a mismatch, the k letters just matched are needle[:k], already known, so k falls back
22	# to the longest border that still fits; the match ends at i, so it starts i - m + 1 letters
23	# earlier.
24	k = 0
25	for i, ch in enumerate(haystack):
26	while k > 0 and ch != needle[k]:
27	k = lps[k - 1]
28	if ch == needle[k]:
29	k += 1
30	if k == m:
31	return i - m + 1
32	return -1

Invariant: After reading haystack[i], k is the length of the longest prefix of needle that ends at i, and lps[j] is the longest proper prefix of needle[:j + 1] that is also its suffix.

See it run

KMP String Matching, step by step

i -k 0lps 0

The top row is haystack. The middle row is needle. The bottom row is lps, the longest border of each needle prefix.

i the letter being read
k the next needle letter to compare; k letters of needle are already matched
border the lps place that was just written or just read

Start: needle has 5 letters, so lps has 5 places. lps is built first, then haystack is scanned once.

haystack

needle

lps

1 / 14

Gotchas1 of 4

The trap
Gotcha 1: Resetting k = 0 on a mismatch
Mistake
```
while k > 0 and ch != needle[k]:
    k = 0
```
Fix
```
while k > 0 and ch != needle[k]:
    k = lps[k - 1]
```
What happens: After k matched letters, the text just read is needle[:k]. Its end can also be the start of needle. A match can then begin inside the failed attempt. k = 0 throws that start away, and the search can miss the match. k = lps[k - 1] keeps it.
Example: haystack = "abababc", needle = "ababc"
Mistake: returns -1Fix: returns 2
Gotcha 2: Building lps with range(m) instead of range(1, m)
Mistake
```
for i in range(m):
```
Fix
```
for i in range(1, m):
```
What happens: lps[0] must stay 0, because a single letter has no shorter border. With range(m), the loop compares needle[0] with itself and sets lps[0] = 1. A fall back from k = 1 then sets k = lps[0], which is 1 again. The while loop never ends.
Example: haystack = "ab", needle = "ac"
Mistake: the loop never endsFix: returns -1
Gotcha 3: Falling back once with if instead of while
Mistake
```
if k > 0 and ch != needle[k]:
```
Fix
```
while k > 0 and ch != needle[k]:
```
What happens: After one fall back, the letter may still not match needle[k]. The search must then fall back again, to a shorter border. With if, it falls back once and moves on. k then counts letters that were never matched.
Example: haystack = "aabaa", needle = "aaa"
Mistake: returns 2Fix: returns -1
Gotcha 4: Falling back to lps[k] instead of lps[k - 1]
Mistake
```
while k > 0 and ch != needle[k]:
    k = lps[k]
```
Fix
```
while k > 0 and ch != needle[k]:
    k = lps[k - 1]
```
What happens: After k matched letters, the text read is needle[:k]. Its border is stored at lps[k - 1], because lps[i] describes needle[:i + 1]. lps[k] describes a prefix one letter longer than what was read. In this example, k is 2 at the b, and lps[2] is also 2. k never changes, so the while loop never ends.
Example: haystack = "aabaaab", needle = "aaab"
Mistake: the loop never endsFix: returns 3

Deep Dive

A mismatch must not send the search backward

Building lps with the same loop

Because the build and the search are the same loop, one idea explains both. k is always the length of the longest prefix of needle that ends at the letter just read.

Find "ababc" in "abababc", traced

At i = 5 the letter "b" gives k = 4. At i = 6 the letter "c" gives k = 5 = m. The match ends at i = 6, so it starts at 6 - 5 + 1 = 2.

Why the cost is O(N + M)

The build follows the same argument on needle, so it costs O(M). The total time is O(N + M). The only extra memory is lps, so the space is O(M).

60-Second Pitch

Common Questions

Why is the time O(N + M) and not O(N * M)?: k goes up by at most 1 for each letter of haystack, and every fall back lowers it. The number of fall backs therefore cannot exceed the number of increases. The scan makes at most about 2N steps, and the build makes at most about 2M steps.
Why lps[k - 1] and not lps[k]?: lps[i] describes needle[:i + 1]. After k matched letters, the text read is needle[:k], so its border is at index k - 1. lps[k] describes a prefix one letter longer than what was read, and the while loop can then run forever.
How do you find every occurrence, not only the first?: When k == m, record i - m + 1 and then set k = lps[m - 1] instead of returning. The next match may overlap this one. On haystack = "aaaaa" and needle = "aa" this finds the starts [0, 1, 2, 3].
How does the same table solve Longest Happy Prefix (LC 1392)?: A happy prefix is a non-empty prefix that is also a suffix and is shorter than the whole string. That is a border, so the answer is s[:lps[m - 1]]. For s = "level" the table ends in 1, and the answer is "l".
Why not use a hash of each window instead?: A rolling hash (Rabin-Karp) compares one number per window and is fast on average. Two different windows can have the same hash, so every hash match needs a letter-by-letter check. KMP has no such case, and its O(N + M) time holds for every input.

SWE Reasoning

Spot it

You must find an exact pattern in a long text in O(N + M), as in Find the Index of the First Occurrence in a String (LC 28).
The question is about a prefix of a string that comes back later in it: a border, a period or a repeated start (Longest Happy Prefix (LC 1392), Repeated Substring Pattern (LC 459), Shortest Palindrome (LC 214)).
The simple search re-reads letters after a mismatch, and the input is large enough for O(N * M) to be too slow.
Letters must match in order. If the pattern may appear with its letters in any order, this is a window of letter counts instead.

The invariant, step by step

lps is built first. lps[j] is the length of the longest border of needle[:j + 1] that is shorter than that prefix.
The search starts with k = 0. k is the number of letters of needle matched at the end of what was read.
For each letter ch of haystack, k falls back with k = lps[k - 1] while k > 0 and ch != needle[k]. Each fall back keeps the longest part that can still start a match.
If ch == needle[k], then k += 1. After this step, k is the length of the longest prefix of needle that ends at ch.
When k == m, the whole needle ends at i, so it starts at i - m + 1. If haystack ends first, the answer is -1.

Traps

Resetting k = 0 on a mismatch. The search forgets a border that was already matched. On haystack = "abababc" and needle = "ababc" it returns -1 instead of 2.
Building lps with range(m). The loop compares needle[0] with itself, sets lps[0] = 1, and a later fall back never ends.
Using if instead of while for the fall back. After one fall back the letter may still differ, so k then counts letters that were never matched.
Using lps[k] instead of lps[k - 1]. lps[i] describes needle[:i + 1], so the border of the k letters read is at lps[k - 1].

Practice

Canonical LeetCode:Find the Index of the First Occurrence in a String (LC 28)Longest Happy Prefix (LC 1392)Repeated Substring Pattern (LC 459)Shortest Palindrome (LC 214)