Z-algorithm
hardThe Z-box remembers the last useful comparison, so most positions are answered by copying from a mirror index. Because the box's right edge never decreases, the whole thing is linear.
O(n)Space O(n)What to notice
z[i] answers one question: how far does the prefix repeat here?
It is the length of the longest substring starting at i that also starts the whole string. Everything the algorithm does is a way to compute that array without re-comparing characters.
The Z-box is memory of the last useful comparison
[l, r) is the rightmost interval known to match a prefix. Inside it, the answer at i can be copied from the mirror position i−l - work already done, reused. Only past r does the algorithm compare characters at all.
Linear because r never decreases
Every explicit character comparison either fails once per position, or succeeds and pushes r further right. r moves at most n times in total, so the whole thing is O(n).
Pattern matching for free
Run it on pattern + separator + text and every index where z equals the pattern length is a match. Same O(n + m) as KMP, and often easier to get right under interview pressure.
Saved in this browser - no sign-up, nothing sent anywhere.
How the Z-algorithm works
The Z-array answers one question at every index: how far does the string's own prefix repeat starting here? z[i] is the length of the longest substring beginning at i that is also a prefix of the whole string. For aabaab, z = [6, 1, 0, 3, 1, 0] - the 3 records that the prefix aab reappears at index 3.
Computing that naively is O(n²). The Z-algorithm keeps a Z-box [l, r) - the rightmost stretch already known to match a prefix. Any i inside the box is sitting in a copy of the prefix, so its answer starts as the mirror value z[i - l], clamped to min(r - i, z[i - l]). Fresh comparisons happen only past r, in text nobody has examined yet.
Linearity falls out of one invariant: every explicit comparison either fails, at most once per position, or succeeds and pushes r further right - and r never decreases, so successes total at most n. To search with it, run the function over pattern + separator + text using a separator found in neither: every index where z equals the pattern length is a match.
Step by step
- Compute z for aabaab. z[0] = 6 by definition - the whole string - and the Z-box [l, r) starts empty.
- i = 1: no box to reuse, compare fresh. s[1] = a matches the prefix, s[2] = b breaks it: z[1] = 1, box [1, 2).
- i = 2: still outside the box. The first comparison, prefix a against s[2] = b, fails - z[2] = 0.
- i = 3: fresh comparisons match a, a, b - z[3] = 3 and the box jumps to [3, 6), the rightmost match so far.
- i = 4: inside the box. The mirror index 4 - 3 = 1 holds z = 1, so z[4] starts at min(2, 1) = 1 with zero comparisons; one extension attempt fails.
- i = 5: the mirror gives 0 and the single extension attempt fails - z[5] = 0. Final array [6, 1, 0, 3, 1, 0], eight comparisons in all.
- For matching, the same function over pattern + separator + text reports an occurrence wherever z equals the pattern's length.
Complexity
| Worst case time | O(n) |
|---|---|
| Space | O(n) |
Explicit comparisons either fail once or push the Z-box right, at most n times.
Reference implementation
Python
def z_function(s):
"""z[i] = length of the longest substring starting at i
that is also a prefix of s."""
n = len(s)
if n == 0:
return []
z = [0] * n
z[0] = n
l = r = 0
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l]) # copy from the mirror position
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1 # extend explicitly
if i + z[i] > r:
l, r = i, i + z[i]
return z
def search(text, pattern):
"""Concatenate with a separator that appears in neither."""
s = pattern + "\x00" + text
z = z_function(s)
m = len(pattern)
return [i - m - 1 for i, v in enumerate(z) if v == m]JavaScript
function zFunction(s) {
const n = s.length, z = new Array(n).fill(0);
z[0] = n;
let l = 0, r = 0;
for (let i = 1; i < n; i++) {
if (i < r) z[i] = Math.min(r - i, z[i - l]);
while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;
if (i + z[i] > r) { l = i; r = i + z[i]; }
}
return z;
}Common pitfalls
- Copying the mirror value without the min(r - i, ...) clamp. The mirror's match can extend past r, where nothing is known - unclamped copies produce wrong values that survive casual testing.
- Moving the box on every iteration instead of only when i + z[i] > r. If r can retreat, the never-decreasing argument breaks and the linear bound goes with it.
- Conventions for z[0] differ - this implementation stores n, others store 0. Downstream code that reads the array must know which convention it was handed.
- Matching with a separator that can occur in the data. If the joint character appears in pattern or text, a fake prefix can span the join and report phantom matches.
Where it is used
- Pattern matching in one pass: z over pattern + separator + text finds every occurrence in O(n + m), rivalling KMP with simpler code.
- Period detection: if i + z[i] = n and i divides n, the string is a repetition of its first i characters.
- Border finding: every i with i + z[i] = n marks a suffix that is also a prefix - all borders in one scan.
- Competitive programming staples - prefix similarity sums and string compression tasks are often the Z-array verbatim.
Frequently asked questions
What is the time and space complexity of the Z-algorithm?
O(n) time and O(n) space for the array. Every explicit character comparison either fails - at most once per position - or succeeds and pushes the box boundary r right, and r never decreases, so at most n successes happen across the whole run. Everything else is copied from the mirror in constant time.
What is the difference between the Z-array and the KMP failure function?
Mirror images of one another. lps[i] looks backwards: the longest proper prefix ending at i that is also a suffix. z[i] looks forwards: how far the whole string's prefix repeats starting at i. Either can be converted to the other in linear time, and both yield O(n + m) matching.
How do you search for a pattern using the Z-algorithm?
Build the string pattern + separator + text, where the separator appears in neither - the reference code joins with a null byte. Compute z over it; every position whose value equals the pattern length m is a full occurrence, at index i - m - 1 of the original text.
Is the Z-algorithm easier to implement than KMP?
Many people find it so: one array, one box, one clamp, and its matching reduction is mechanical, which makes it a safer choice under interview pressure. KMP still matters when a problem needs the failure table itself - several classic questions do - and both run in O(n + m).