Pebellslearn by building
0%
RoadmapsMatrixCoursesSandboxSign in
String Algorithms  ›  Lesson

The Z Algorithm

The Z Algorithm 28 minInside the Z-box, values are copied from their mirror, so each character is compared only a constant number of times
You're building a piece ofQuarry — the text index
This piece — z_array(): For every position, how far the text there repeats its own beginning.
Scenario A user starts typing "disk f" into Quarry's search box. For every position in the log, the prefix profiler already knows how much of the query's beginning appears there, so it can rank suggestions without scanning again.
Your task
Build z_array(s): return a list z where z[i] is the length of the longest common prefix of s and s[i:], with z[0] = len(s) and [] for an empty string. Keep a Z-box [l, r), start each value inside it at min(r - i, z[i - l]), and compare characters only past what's known. Example: z_array("aabaaab") → [7, 1, 0, 2, 3, 1, 0].

The Z Algorithm

In short: the Z-array answers the mirror question to KMP's — z[i] is how far the string starting at i copies the string's own beginning. A Z-box [l, r) remembers the furthest-right match found so far; inside it, a new value starts at min(r − i, z[i − l]) from its mirror position and only extends past what's already known, which keeps the whole scan at O(n). Gluing pattern + separator + text and reading where z equals the pattern's length turns the same algorithm into a search.

![A Z-box 4, 7) on "aabaaab"; z[5] is copied from its mirror z[1] = 1 with no character comparison

KMP answers "how much of the pattern is matched ending here?" The Z algorithm answers the mirror-image question: "how much of the string's beginning is repeated starting here?" Both run in linear time. Z is often the easier of the two to get right under pressure, because its invariant is something you can draw: a box.

The Z-array

For a string s, z[i] is the length of the longest common prefix of s and s[i:], meaning how many characters starting at i copy the start of the string. By convention here z[0] = len(s), since the whole string trivially copies itself.

i 0 1 2 3 4 5 6
s a a b a a a b
z 7 1 0 2 3 1 0

z[4] = 3 because s[4:] is aab, which starts the same way as s for three characters. z[2] = 0 because b doesn't match a at all.

In Quarry this is the prefix profiler. For every position in a block of text, it says how far the text there echoes a given beginning. Pattern search comes straight out of it: glue the pattern, a separator and the text together, and every position where z equals the pattern's length is a match.

The direct way compares from scratch at every position:

python
What does this print?
s = "aaaa"
z = [len(s)]
for i in range(1, len(s)):
    k = 0
    while i + k < len(s) and s[k] == s[i + k]:
        k += 1
    z.append(k)
print(z)

The Z-box

The waste in naive_z is that it forgets what it has learned. Suppose some earlier position l had a long match, so that s[l:r] is a copy of s[0:r-l]. Call [l, r) the Z-box: the matched stretch that reaches furthest to the right.

Now take a position i inside the box. Because the box is a copy of the string's start, the text from i to r is a copy of the text from i − l to r − l. And you already computed z[i − l]. So before comparing anything:

z[i]≥min⁡(z[i−l],  r−i)z[i] \ge \min\big(z[i-l],\; r-i\big)

That leaves two cases, and they are the whole algorithm:

  1. Copy. If z[i − l] < r − i, the mirrored match ended strictly inside the box, so this one ends at the same place. z[i] = z[i − l] exactly, with no comparisons.
  2. Extend. If z[i − l] reaches the edge of the box or beyond, you know z[i] is at least r − i, but the box can't tell you anything past r. Compare characters from r onwards, then move the box to [i, i + z[i]).

If i is outside every box so far, it's case 2 with nothing known: compare from scratch.

watch it move · grid

Inside the Z-box a value is either copied from its mirror with no comparisons, or known up to the box's edge and extended from there. Outside the box, comparisons start from scratch.

i = 1 with no box yet, so compare from scratch. s[0] = a matches s[1] = a, then s[1] = a meets s[2] = b and stops. 2 by 7 table. At row 1, column 1 — value empty. 8 of 14 cells filled.

1 / 9

The code

python

In the copy case the while loop still runs one comparison, and it fails at once. A variant that skips the loop when z[i - l] < r - i saves that one check. Either way the bound below holds.

What does this print?
def z_array(s):
    n = len(s)
    z = [0] * n
    if n:
        z[0] = n
    l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

print(z_array("abacaba"))

Step through the loop on a short periodic string and watch l and r move:

step through it
1s = "abab"
2n = len(s)
3z = [n] + [0] * (n - 1)
4l = r = 0
5for i in range(1, n):
6 if i < r:
7 z[i] = min(r - i, z[i - l])
8 while i + z[i] < n and s[z[i]] == s[i + z[i]]:
9 z[i] += 1
10 if i + z[i] > r:
11 l, r = i, i + z[i]
12print(z)

The min is not optional. Without it, a mirrored value can claim characters beyond the box, where nothing is known:

broken — fix it

From position 2 only two characters remain, so z[2] must be 2. This prints [4, 3, 3, 3].

Now run your own. Each frame shows the box as a highlighted stretch of s, the mirror position being copied from, and the value just written. Try "abaabaab", "abcd", or the fix bug above:

your code, drawn · grid

Your Z-array, one value per frame. The highlighted cells are the box, and a copied value comes from its marked mirror.

Why it's O(n)

Every comparison in the while loop either succeeds or fails.

  • A failure ends the loop, so there is at most one per position: n in total.
  • A success at i + z[i] ≥ r pushes the right edge of the new box one step further. Successes can never happen inside the old box, because z[i] starts at min(r − i, …), which is already at or past what's known. And r never moves left and never passes n, so there are at most n successes in total.

So there are at most 2n comparisons, the same shape of argument as KMP's: a quantity that only goes one way pays for the work.

On a run of nn identical characters, the naive loop does about n(n−1)/2n(n-1)/2 comparisons against Z's 2n2n:

n naive Z bound ratio
10 45 20 2.25
100 4,950 200 24.75
401 80,200 802 100
1,000 499,500 2,000 249.75

The ratio is (n−1)/4(n-1)/4, which reaches 100 at n=401n = 401. Four hundred identical bytes is one line of padding in a log file.

Z for search, and a sentinel trick

To find p in t, compute the Z-array of p + separator + t. The separator stops any match from running past the pattern into the text, so a value can never exceed len(p), and a value equal to len(p) marks an occurrence. If the text might contain any character you would pick as a separator, don't use a character at all. z_array only indexes and compares, so it works on a list, and None never equals a character:

python

An interview question. A user types a query that has a typo near the end. Find the longest prefix of the query that appears anywhere in the document. That is the function above: one Z-array over query + [None] + doc, and the largest value in the document part. It runs in O(|query| + |doc|). Checking each prefix with in would cost a full scan per prefix.

❓ Cross-question — "When do I reach for Z instead of KMP?" Both are linear. π describes matches ending at each position, which suits streams, because you never need to see ahead. Z describes matches starting at each position, which suits whole-string questions: periods, how often each prefix occurs, and anything you can solve by running it forwards and then on the reversed strings. That last trick is how the capstone exercise below allows one typo.

What it costs

naive Z Z algorithm
time O(n²) on repetitive text O(n), at most 2n comparisons
extra memory O(n) for the array O(n) for the array
search for p in t O(len(p) · len(t)) O(len(p) + len(t)) via p + [None] + t

Idioms & real-world patterns

  • z[i] = min(r - i, z[i - l]), then extend. That one line is the algorithm.
  • Concatenate with a sentinel (list(p) + [None] + list(t)) to turn "search" into "compute one Z-array".
  • Run it both ways. Z on the strings gives prefix matches, and Z on the reversed strings gives suffix matches. Combined, they answer "matches with one mismatch" in linear time.
  • z[p] == n − p means p is a period of s: shifting s by p lines up with itself.
  • Where it lives: read alignment in bioinformatics as a fast filter, compression tools looking for the longest earlier repeat, and competitive programming, where it's the linear-time string tool people reach for first.

Quick practice

What does this print?
s = "abcabcabc"
z = [len(s)]
for i in range(1, len(s)):
    k = 0
    while i + k < len(s) and s[k] == s[i + k]:
        k += 1
    z.append(k)
print(z)
What does this print?
def z_array(s):
    n = len(s)
    z = [0] * n
    if n:
        z[0] = n
    l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

s = "abcabcabc"
z = z_array(s)
n = len(s)
print([p for p in range(1, n) if z[p] == n - p])

🎯 Your turn

Build z_array(s), Quarry's prefix profiler. Return the list z where z[i] is the length of the longest common prefix of s and s[i:], with z[0] = len(s), and [] for an empty string. Keep a Z-box [l, r), start each value at min(r − i, z[i − l]) inside it, and extend with comparisons only past what's known.

  • z_array("aabaaab") → [7, 1, 0, 2, 3, 1, 0]
  • z_array("aaaa") → [4, 3, 2, 1]

Then press ▶ Run, tap the Live App try chips, and hit ✓ Check.

Practice — level up

0/6 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upShared beginning

Write common_prefix_len(a, b) returning how many characters a and b share at the start, stopping at the first difference or at the end of the shorter string. This is the question each Z-value answers. common_prefix_len("disk full", "disk fault") → 6.

z-arraystrings
DrillSearch with one Z-array

Write z_find(text, pattern) returning every start index of pattern in text (overlaps included) using one Z-array of pattern + separator + text. Build it as a list with None as the separator, so no character in the text can accidentally match it. An empty pattern returns []. z_find("abcabcab", "cab") → [2, 5].

z-algorithmstring-matching
BuildEvery period

A string s has period p if s[i] == s[i + p] for every i where both exist, meaning a copy of s shifted by p lines up with itself. len(s) always counts. Write all_periods(s) returning every period of s in increasing order, in O(n), from one Z-array. all_periods("abaaba") → [3, 5, 6], and an empty string returns [].

z-arrayborder
BossHow often each prefix occurs

Quarry's autocomplete wants to know how common each beginning of a term is inside it. Write prefix_counts(s) returning a list c where c[k - 1] is the number of times the length-k prefix of s occurs in s (overlaps count, and the prefix itself counts once). Do it in O(n): a prefix of length k starts at i exactly when z[i] >= k. prefix_counts("abab") → [2, 2, 1, 1].

z-algorithmstring-matching
CapstoneOne typo allowed

Quarry's search forgives one typo. Write near_matches(text, pattern) returning every start i where text[i:i + len(pattern)] differs from pattern in at most one position (a substitution, not an insertion or deletion). An empty pattern returns []. Aim for O(n + m): one Z-array gives, at every start, how many characters match from the front, and a second Z-array on the reversed strings gives how many match from the back. near_matches("abcabd", "abd") → [0, 3].

z-algorithmstring-matching
ExplainCopy or extend

In the Z algorithm, a position inside the Z-box sometimes gets its value with no comparisons and sometimes has to compare characters. Explain which case is which and why, and then why the total number of comparisons is at most about 2n.

z_array.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
z_array(s) → listFor each position, how many characters starting there copy the start of the string.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.