KMP Prefix Function
Find a pattern in O(n + m).
KMP Prefix Function is a free Coding Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Pattern-Matching Problem
You want to find where a small pattern appears inside a big text. Naive checks are slow, so contests reward a smarter scan. 🔍
Why Naive Search Hurts
Comparing the pattern at every position can cost O(n*m) time. On large inputs that quietly blows your time limit.
Meet the Prefix Function
The prefix function measures, at each position, the longest proper prefix that is also a suffix. It is the heart of KMP.
Proper Prefix and Suffix
A proper prefix or suffix skips the whole string itself. For ababa the longest matching pair has length 3: aba.
What pi[i] Stores
We store the values in an array called pi. Here pi[i] is that longest prefix-suffix length for the slice ending at index i.
Building pi in One Pass
You build pi left to right, reusing earlier values instead of rechecking from scratch. That reuse is the whole trick.
def prefix_function(s):
pi = [0] * len(s)
return piThe Fallback Loop
When characters mismatch, you fall back to pi[k-1] instead of resetting to zero. This avoids redoing work.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Extending a Match
If the current characters match, you grow the length by one and record it. Mismatches at zero just stay zero.
if s[i] == s[k]:
k += 1
pi[i] = kSearching with the Trick
To search text for a pattern, glue them as pattern + sep + text. Any pi value equal to the pattern length marks a full match.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Why a Separator Matters
The separator is a symbol not in either string. It stops matches from leaking across the join and giving false hits.
Linear Time Payoff
Both building and searching run in O(n + m). Every character is processed once, so KMP scales to huge contest inputs.
Quick Check
Test your grip on what the prefix function records.
Recap: KMP in a Nutshell
You learned the prefix function: build pi once, fall back on mismatches, and search in linear time. That is KMP in a nutshell. 🎯
Frequently asked questions
Is the “KMP Prefix Function” lesson free?
Yes — the full text of “KMP Prefix Function” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “KMP Prefix Function”?
Find a pattern in O(n + m). You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “KMP Prefix Function” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.