1. Z array
z[i] is the length of the longest substring at i matching the prefix.
const z = new Array(n).fill(0)Typorithm · hard
Z-Function
▷ Interactive algorithm labz-functionstring-algorithmsz-arrayz-boxprefix-match
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Z-Function
String Algorithms
Compute z[i], the longest prefix match starting at i, reusing a [left, right] z-box to stay linear.
The Z-array gives, for each index, how far the substring there matches the string's own prefix.
A maintained [left, right] window (the z-box) lets earlier results be reused instead of recomputed.
Combined with extend-and-update, the whole array is built in O(n).
Preparing algorithm lab…
01
z[i] = prefix match length at i.
02
Reuse z inside the [left, right] box.
03
Extend, then update the box.
function zFunction(s) {
const n = s.length;
const z = new Array(n).fill(0);
let left = 0;
let right = 0;
for (let i = 1; i < n; i += 1) {
if (i < right) {
z[i] = Math.min(right - i, z[i - left]);
}
while (i + z[i] < n && s[z[i]] === s[i + z[i]]) {
z[i] += 1;
}
if (i + z[i] > right) {
left = i;
right = i + z[i];
}
}
return z;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Reuse the box
Inside the current [left, right] box, reuse a previously computed z value.
z[i] = Math.min(right - i, z[i - left])3. Extend match
Grow the match by comparing prefix characters directly.
while (i + z[i] < n && s[z[i]] === s[i + z[i]])4. Update box
If the match reaches further, move the [left, right] box forward.
if (i + z[i] > right)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.