Z-Function for Pattern Search
Match prefixes across the string.
Z-Function for Pattern Search is a free Coding Interview Prep lesson on CoddyKit. This is 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, and your progress syncs across the web and the CoddyKit app. The Coding Interview Prep course includes 4 lessons in total.
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. 🎯
Learn Coding Interview Prep with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 90
- Lessons
- 360
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. 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. The Coding Interview Prep course includes 4 lessons in total.
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, so you can start here or from the beginning and move at your own pace. This is lesson 3 of 4.
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