Z-Function for Pattern Search
Match prefixes across the string.
Z-Function for Pattern Search is a free Coding Interview Prep lesson on CoddyKit — lesson 3 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.
Another Matching Tool
The Z-function is a clean alternative to KMP for pattern search. Many find it easier to reason about. ✨
What z[i] Means
For each index, z[i] is the length of the longest substring starting at i that also matches a prefix of the whole string.
A Tiny Example
For aabaab, z reads 0,1,0,3,1,0. At index 3 the run aab matches the prefix, giving length 3.
The Z-Box
We track a window [l, r], the rightmost match found so far. It lets us reuse earlier comparisons.
l, r = 0, 0Inside the Box
When i sits inside the box, you copy a known z value as a head start, capped by the box edge.
if i < r:
z[i] = min(r - i, z[i - l])Extending Past the Box
After the head start, you keep comparing characters one by one as long as they match the prefix.
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1Sliding the Box Forward
If your match reaches further right, you update l and r so future indices can reuse it.
if i + z[i] > r:
l, r = i, i + z[i]Linear Time Guarantee
The box only moves right, so total work is O(n). Each character contributes a bounded amount.
Searching with Z
Concatenate pattern + sep + text and run Z. Any z value equal to the pattern length is a match.
combined = pattern + chr(0) + text
z = z_function(combined)Reading Off Matches
Scan the Z-array; wherever z[i] == len(pattern), the match begins at the matching spot in the text.
if z[i] == len(pattern):
matches.append(i - len(pattern) - 1)Z vs KMP
Z and KMP both run in linear time. Z is often simpler to code, so it is a great backup in your toolkit.
Quick Check
Make sure the meaning of the Z-array is locked in.
Recap: Z-Function Wins
You built the Z-array with a sliding box, searched in linear time, and now have a clean KMP alternative. 🎯
Frequently asked questions
Is the “Z-Function for Pattern Search” lesson free?
Yes — the full text of “Z-Function for Pattern Search” 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 “Z-Function for Pattern Search”?
Match prefixes across the string. 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 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Z-Function for Pattern Search” 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.
All lessons in this course
- KMP Prefix Function
- Polynomial String Hashing
- Z-Function for Pattern Search
- Tries for Prefix Lookups