How to Learn the Z Algorithm: Prefix Matches, Z-Boxes, Linear-Time String Search and Periodicity

Wait, What?

A string can tell you, at every position, how much of its own beginning reappears there—and all of those answers can be computed in linear time.

The Z algorithm computes a compact description of prefix matches across a string. It is a superb teaching algorithm because the naive definition is obvious, the optimized version reuses proven work, and the proof of linear time comes from one moving boundary rather than from complicated recurrence solving.

Quick Answer

Learn the Z algorithm through Z-array meaning → naive comparisons → rightmost Z-box → reuse inside the box → extension beyond the box → linear-time proof → pattern matching → borders and periods → production edge cases. If you can explain exactly what z[i] means before writing code, the implementation becomes much easier to reason about.

1. Define the Z-Array Precisely

For a string s of length n, z[i] is the length of the longest substring beginning at position i that matches a prefix of s.

For example, with s = "aabxaab", the substring beginning at index 4 is "aab", which matches the first three characters of the string. Therefore z[4] = 3.

The value at index 0 is conventional rather than algorithmically important; many implementations set z[0] = 0, while some definitions use n. State your convention.

2. The Naive Version Reveals the Real Job

for i from 1 to n-1:
    while i + z[i] < n and s[z[i]] == s[i + z[i]]:
        z[i] += 1

This directly implements the definition, but repeated strings can cause the same characters to be compared again and again. In the worst case, the work becomes quadratic.

The optimized algorithm asks a better question: what prefix equality have we already proved that can be reused at this index?

3. The Z-Box Is the Reusable Proof

Maintain a half-open interval [l, r) representing the rightmost substring already known to match the prefix:

s[l:r] == s[0:r-l]

If the current index i lies outside the box, there is no reusable information and we compare from zero. If i lies inside the box, then position i corresponds to prefix position i-l. We can copy a previously known Z-value—but only up to the right edge of the box.

4. The Key Initialization

When i < r, initialize:

z[i] = min(r - i, z[i - l])

The minimum matters. A mirrored Z-value may extend beyond the current box, and equality beyond r has not yet been proved. Reusing more than r-i would turn an inference into a guess.

5. Then Extend Only Where Knowledge Ends

After the safe initialization, compare characters directly while the prefix match continues. If the match reaches farther right than the current box, update l and r.

z_function(s):
    n = len(s)
    z = array of n zeros
    l = r = 0

    for i from 1 to n-1:
        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 = i
            r = i + z[i]

    return z

6. Why the Algorithm Is Linear

The inner while loop looks dangerous because it sits inside a loop over all positions. The proof is that expensive successful comparisons outside existing knowledge move r to the right. The boundary r never moves left and can advance at most n times.

Work inside the current box is reused through previously computed Z-values. Fresh extension work happens only at the frontier. That gives O(n) time.

7. Trace the Box, Not Just the Array

When learning, make a table with columns i, l, r, mirrored index, initial z[i], extension comparisons, final z[i]. This exposes the distinction between copied information and newly verified characters. Novices who look only at the final Z-array often miss the invariant that makes the optimization correct.

8. Pattern Matching With One Concatenated String

To find a pattern P in text T, form:

P + separator + T

Choose a separator that cannot occur in either input. Compute the Z-array. Any position in the text portion where the Z-value is at least len(P) marks a pattern occurrence. Total running time is O(|P| + |T|).

In production systems with arbitrary binary data or unrestricted Unicode, do not casually assume a magic character is absent. Use a representation that makes the separator logically distinct, or perform the comparison without sentinel collision risk.

9. Borders and Periodicity Fall Out Naturally

A border is a string that is both a proper prefix and suffix. Position i begins a suffix; if i + z[i] == n, then the suffix starting at i matches a prefix of length z[i], revealing a border.

Periodicity can also be tested with Z-values. If a candidate period length p divides n and the suffix from p matches the prefix for the remaining n-p characters, then the string consists of repeated copies of a block of length p.

10. Z Algorithm Versus KMP

Both can support linear-time exact pattern matching, but they encode different information. KMP’s prefix/failure structure asks how a matched prefix can fall back after mismatch. The Z-array asks how much of the whole prefix matches at every starting position.

Neither is universally “better.” The best choice depends on which string structure the rest of the problem needs. A professional learner should be able to translate the same pattern-search problem into either representation and explain the different invariants.

11. Production Edge Cases

• Empty pattern: define the API contract explicitly.
• Separator collisions: avoid assumptions about the input alphabet.
• Index conventions: be consistent about inclusive [l,r] versus half-open [l,r) Z-boxes.
• Unicode: decide whether indexing is by bytes, code points or grapheme clusters.
• Streaming text: the standard Z construction assumes random access to the combined string; a different design may be better for unbounded streams.

12. How to Learn It Efficiently

Use worked traces before implementation. Programming-education research on subgoal-labelled examples and code tracing suggests that learners benefit when procedural steps are grouped by purpose. For the Z algorithm, use the subgoals locate relative position → reuse proven prefix match → cap at the known boundary → extend with fresh comparisons → update the frontier. Then remove the labels and reconstruct them from memory.

Common Failure States

• Defining z[i] vaguely as “number of matching characters” without saying matching the prefix.
• Copying z[i-l] without capping it at r-i.
• Mixing inclusive and half-open box boundaries.
• Updating the box even when the new match does not extend farther right.
• Claiming linear time without explaining why r advances only O(n) times.
• Using a separator that may occur in the data.
• Forgetting to translate combined-string indices back to text indices.

Practice Ladder

• Beginner: compute Z-arrays by definition for short strings.
• Foundation: trace l and r on repetitive strings such as aaaaaa and aabaaab.
• Intermediate: implement linear Z construction and pattern matching.
• Advanced: derive border and period queries from the Z-array.
• Professional: test binary alphabets, Unicode indexing choices, very long repetitive inputs and API edge cases.
• Verification: compare the optimized Z-array against the naive O(n²) definition on thousands of small random strings.

Learning Hall Boundary

This article owns the Z-function/Z algorithm as a prefix-matching primitive, including the Z-box invariant, linear construction, exact pattern matching and representative border/period applications. It does not replace existing general string-matching, KMP, suffix-array, suffix-tree, FM-index, MindOS or Student/Studying Interface canonical jobs.

Evidence Boundary

Dan Gusfield’s UC Davis string-algorithm materials and Algorithms on Strings, Trees and Sequences are foundational references for Z-based exact matching. The Algorithms for Competitive Programming Z-function reference, updated in July 2026, documents the standard half-open Z-box implementation, linear-time argument and applications. The learning progression here is informed by research on code tracing, PRIMM and subgoal-labelled worked examples in programming education.

Professional rule: you understand the Z algorithm when you can say what information is already proved inside the current box, what information remains unknown beyond it, and why only frontier extension contributes new linear work.