The Z-algorithm answers a single question for every position: how long is the substring here that matches the string’s own prefix? That one array — the Z-array — turns out to encode enough information to do pattern matching in linear time, with a cleaner invariant than KMP. And unlike many linear-time algorithms, its correctness argument is almost visual.

How It Works

For a string S, the Z-array stores at each position i: z[i] = the length of the longest substring starting at i that matches a prefix of S.

1. Build the joined string for pattern matching: S = pattern + "$" + text. The separator guarantees no match can span the boundary.
2. Maintain the Z-box: track [l, r], the rightmost segment that matches a prefix.
3. Compute each z[i]:
   • If i lies inside the box, seed z[i] from z[i − l], capped at r − i + 1.
   • Then extend while characters agree.
4. Read off matches: every i past the separator with z[i] == m is a pattern occurrence at i − m − 1.

Key Insight

When i is inside the current Z-box, the substring at i mirrors the substring at i − l (both start inside the same prefix match), so z[i] can be seeded from already-computed z[i − l] instead of starting from scratch. Extensions only ever advance the right edge r, so across the entire algorithm the total extension work is O(n) — the “each character is touched once” argument, in its cleanest form.

Worked Example

The visualizer matches pattern GEEK against GEEKSFORGEEKS, using the joined string S = GEEK$GEEKSFORGEEKS.

The Z-array:

   S:  G E E K $ G E E K S F O R G E E K S
 z[i]: 0 0 0 0 0 4 3 2 1 0 0 0 0 3 2 1 0 0

• z[5] = 4 (m = 4) → match at text position 5 − 4 − 1 = 0.
• z[13] = 3 → prefix match of length 3, but 3 < 4, so no full match there.

The final report: GEEK occurs at text positions 0 and 8. Watch how z[6], z[7], z[8] are seeded from z[1], z[2], z[3] because they all sit inside the first Z-box [5, 8] — no re-comparison needed.

Edge Cases & Pitfalls

• Separator choice: $ must not appear in pattern or text, or a match could “fake” across the boundary.
• Seeding cap: inside the box, z[i] = min(z[i − l], r − i + 1) — the seed is capped by the box’s right edge or it would overclaim.
• Positions after the separator: matches are only valid for i > m; don’t read matches from the pattern’s own prefix region.
• Empty pattern / empty text: define the Z-array over the empty string explicitly to avoid off-by-one loops.

Comparison: Z-Algorithm vs KMP

Applications

• Linear-time pattern matching — simpler invariant than KMP
• Prefix-matching problems — longest repeated substring, compression (LZ77-style)
• Text algorithms pedagogy — the Z-box invariant transfers to Manacher’s algorithm

Practice Trajectory

1. Hand-build the Z-array for GEEK$GEEK... and confirm z[5] = 4.
2. Explain why z[6], z[7], z[8] reuse earlier values instead of re-comparing.
3. Read off both matches (positions 0 and 8) from the Z-array.
4. Change the pattern to GEEKS and recompute — note how the second occurrence becomes exact.
5. Prove the total work is O(n) by tracking how r only moves right.