The Z-Algorithm

Suppose you have a pattern pat and a long text txt, and you want to know every position where pat appears. The naive approach re-reads the pattern from scratch at each position — $O(n \cdot m)$ comparisons and painfully slow on repetitive data.

The Z-algorithm, introduced as part of the classical string-algorithm canon (Gusfield's 1997 textbook gives the cleanest exposition), takes a completely different view. Concatenate the pattern and text with a sentinel that does not appear in either — Z-string = pat + '$' + txt — and build the Z-array: for every index $i$, Z[i] is the length of the longest substring starting at $i$ that also matches a prefix of the full Z-string.

Once you have the Z-array, finding every match is trivial: any position $i$ (inside the text portion) where Z[i] equals the length of the pattern is exactly a match. The entire computation — building the array and scanning for matches — runs in $O(n + m)$ time with $O(n + m)$ extra space and no hash tables.

The key insight that keeps the algorithm linear is the Z-box: the algorithm maintains the rightmost interval [l, r] where a prefix match is already known. When processing position $i \le r$, it can initialize Z[i] from a previously computed value Z[i-l] instead of comparing from scratch. Each character is examined at most twice: once when it extends the Z-box to the right, and possibly once more to verify the new boundary. The total comparison count is $O(n + m)$.

This is in the same family as KMP pattern matching — both solve the problem in linear time — but the Z-array is often easier to implement from scratch and reasons more explicitly about prefix structure.

Type a pattern and a text below. The demo builds the combined Z-string pattern$text, computes the Z-array with one linear scan, and highlights every position where a match is found.

<div class="controls">
  <label>{{label_pattern}} <input id="pat" type="text" value="ab" maxlength="12" spellcheck="false"></label>
  <label>{{label_text}} <input id="txt" type="text" value="ababcabab" maxlength="40" spellcheck="false"></label>
</div>
<div class="legend">
  <span class="leg-box sep"></span>{{legend_sep}}&nbsp;&nbsp;
  <span class="leg-box match"></span>{{legend_match}}&nbsp;&nbsp;
  <span class="leg-box zval"></span>{{legend_zval}}
</div>
<div class="section-label">{{label_zstring}} <span id="zstr-label"></span></div>
<div id="cells" class="cells"></div>
<div id="matches" class="matches"></div>
<div class="info">
  <strong>{{info_heading}}</strong> {{info_body}}
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.controls { display: flex; gap: 1rem; flex-wrap: wrap; margin-bottom: .8rem; }
.controls label { display: flex; flex-direction: column; font-size: .82rem; font-weight: 600; color: #555; gap: .2rem; }
.controls input { font: 500 15px ui-monospace, monospace; padding: .35rem .55rem; border: 1.5px solid #bcc5d0; border-radius: 7px; width: 180px; outline: none; }
.controls input:focus { border-color: #4a7fbf; }
.legend { font-size: .8rem; color: #555; margin-bottom: .35rem; display: flex; align-items: center; gap: .2rem; }
.leg-box { display: inline-block; width: 14px; height: 14px; border-radius: 3px; vertical-align: middle; }
.leg-box.sep { background: #e0c060; }
.leg-box.match { background: #3aaa6e; }
.leg-box.zval { background: #5a9fd4; }
.section-label { font-size: .8rem; color: #666; margin-bottom: .3rem; font-family: ui-monospace, monospace; }
.cells { display: flex; flex-wrap: wrap; gap: 3px; margin-bottom: .7rem; }
.cell { display: flex; flex-direction: column; align-items: center; min-width: 32px; }
.cell .ch { font: 700 14px ui-monospace, monospace; background: #e8eef3; border: 1px solid #cdd5de; border-radius: 5px 5px 0 0; padding: 3px 6px; min-width: 28px; text-align: center; }
.cell .zv { font: 600 12px ui-monospace, monospace; background: #5a9fd4; color: #fff; border-radius: 0 0 5px 5px; padding: 2px 6px; min-width: 28px; text-align: center; }
.cell.is-sep .ch { background: #f5e27a; border-color: #d4b840; }
.cell.is-sep .zv { background: #c8a520; }
.cell.is-match .ch { background: #b8f0d4; border-color: #3aaa6e; font-weight: 900; }
.cell.is-match .zv { background: #3aaa6e; }
.cell.is-pat .ch { background: #dde8f5; border-color: #5a9fd4; }
.matches { font-size: .92rem; font-weight: 600; min-height: 1.4em; margin-bottom: .6rem; }
.matches.found { color: #1a7a4a; }
.matches.none { color: #b03030; }
.info { font-size: .82rem; color: #555; line-height: 1.55; border-top: 1px solid #e0e5ea; padding-top: .55rem; }
.info code { background: #f0f3f7; padding: .1em .35em; border-radius: 4px; font-size: .9em; }

// Code not found

Each colored cell shows the Z-value at that position — how many characters starting there match the prefix of the full Z-string. Cells in the text portion where the Z-value equals the pattern length are marked as matches. Notice that no position is ever compared from scratch if it falls inside a previously computed Z-box; that is exactly why the algorithm stays linear regardless of how repetitive the data is.

The Z-algorithm is a solved, efficient algorithm — not a hard or open problem, but a fundamental tool with provably optimal characteristics for its task.

Status: solved. The algorithm runs in $\Theta(n+m)$ time and $\Theta(n+m)$ space (where n = text length and m = pattern length), which is also optimal: any algorithm that reads every character at least once needs at least $O(n + m)$ time.

Why is it linear? The proof rests on two observations about the Z-box [l, r]:

1. Every time a character comparison extends $r$, the right boundary moves one step to the right. Since $r$ starts at 0 and can move at most $n + m$ times total, at most $n + m$ extension comparisons happen across the entire run.
2. All other comparisons are lookups into previously computed Z-values — $O(1)$ each. They do not extend $r$, so they are bounded by the number of positions, also $n + m$.

Total comparisons: at most $2(n + m)$ — strictly linear.

Comparison with alternatives:

The Z-algorithm uses slightly more space than KMP (stores the full Z-string) but is often preferred in competitive programming because the invariant is easier to state and verify. It is in the complexity class P — efficiently solvable — unlike the intractable problems explored in articles like P vs NP.

Pattern matching is one of the most frequently needed string operations, and the Z-algorithm's linear guarantee makes it practical across many domains:

• Text editors and search tools: every "Find" and "Find & Replace" operation in editors, grep, and ripgrep relies on fast substring search; linear algorithms are essential for large files.
• Bioinformatics and genomics: searching for gene sequences or protein motifs inside billion-character genomes requires algorithms that are provably linear — the naive approach would take years.
• Network intrusion detection: systems like Snort scan network payloads for thousands of patterns simultaneously; understanding the linear foundation helps reason about throughput guarantees.
• Data compression preprocessing: finding repeated substrings (an LZ-family concept) is closely related to prefix-match reasoning; the Z-array is a stepping stone to suffix arrays and the BWT used in modern compressors.
• Competitive programming: the Z-algorithm is a standard tool taught alongside pattern matching because it is short to implement and its proof is self-contained.
• String periodicity: Z[i] + i == n (where n is the string length) reveals periods; the Z-array can detect the shortest period of a string in linear time.

Wherever text must be searched quickly and reliably — without the probabilistic risk of hash collisions — the Z-algorithm provides a clean, deterministic $O(n + m)$ guarantee.

The Z-algorithm is a beautiful example of how the right invariant — maintaining the rightmost known prefix-match window — turns a problem that naively takes quadratic time into one that takes linear time.

It does not involve randomness, amortized tricks, or complex data structures. One array, one left-to-right pass, one simple rule: if the current position falls inside the Z-box, initialize from a precomputed value; otherwise extend by comparing characters. Every character is touched at most twice, and the total work is provably $O(n + m)$.

In a landscape full of problems where we desperately want efficient algorithms but cannot prove they exist — see P vs NP — the Z-algorithm stands as a reminder that sometimes the efficient solution is clean, correct, and sitting right in front of us.