Introduction

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⋅m)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 ii, Z[i] is the length of the longest substring starting at ii that also matches a prefix of the full Z-string.

Once you have the Z-array, finding every match is trivial: any position ii (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)O(n + m) time with O(n+m)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≤ri \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)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.

Try It

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>Pattern <input id="pat" type="text" value="ab" maxlength="12" spellcheck="false"></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>Separator&nbsp;&nbsp;
  <span class="leg-box match"></span>Match&nbsp;&nbsp;
  <span class="leg-box zval"></span>Z-value (other)
</div>
<div class="section-label">Z-string: <span id="zstr-label"></span></div>
<div id="cells" class="cells"></div>
<div id="matches" class="matches"></div>
<div class="info">
  <strong>How it works:</strong> Build <code>pattern$text</code>. For each position <em>i</em>, <code>Z[i]</code> = longest prefix match. Positions in the text where <code>Z[i] = |pattern|</code> are matches.
</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Z-algorithm: for string s, Z[i] = length of longest substring starting
// at s[i] that matches a prefix of s. Z[0] is conventionally set to 0 (or |s|).
function computeZ(s) {
  const n = s.length, Z = new Array(n).fill(0);
  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;
}

function render() {
  const pat = document.getElementById('pat').value;
  const txt = document.getElementById('txt').value;
  if (!pat || !txt) {
    document.getElementById('cells').innerHTML = '';
    document.getElementById('matches').textContent = '';
    document.getElementById('zstr-label').textContent = '';
    return;
  }
  const sep = '


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.

;
  const s = pat + sep + txt;
  const Z = computeZ(s);
  const patLen = pat.length;
  const cellsEl = document.getElementById('cells');
  const matchesEl = document.getElementById('matches');
  document.getElementById('zstr-label').textContent = '"' + s + '"';

  cellsEl.innerHTML = '';
  const matchPositions = [];

  s.split('').forEach((ch, i) => {
    const isSep = (i === patLen);
    const isPat = (i < patLen);
    const textIdx = i - patLen - 1; // 0-based index in txt
    const isMatch = !isPat && !isSep && Z[i] === patLen;
    if (isMatch) matchPositions.push(textIdx);

    const cell = document.createElement('div');
    cell.className = 'cell' + (isSep ? ' is-sep' : isMatch ? ' is-match' : isPat ? ' is-pat' : '');

    const chDiv = document.createElement('div');
    chDiv.className = 'ch';
    chDiv.textContent = ch;

    const zvDiv = document.createElement('div');
    zvDiv.className = 'zv';
    zvDiv.textContent = i === 0 ? '—' : Z[i];

    cell.appendChild(chDiv);
    cell.appendChild(zvDiv);
    cellsEl.appendChild(cell);
  });

  if (matchPositions.length > 0) {
    matchesEl.className = 'matches found';
    const list = matchPositions.map(p => fmt('%p% ("…%txt%…")', { p: p, txt: txt.slice(p, p + patLen) })).join(', ');
    matchesEl.textContent = fmt(matchPositions.length > 1 ? '✓ Pattern found at text positions: %list%' : '✓ Pattern found at text position: %list%', { list: list });
  } else {
    matchesEl.className = 'matches none';
    matchesEl.textContent = '✗ Pattern not found in text.';
  }
}

document.getElementById('pat').addEventListener('input', render);
document.getElementById('txt').addEventListener('input', render);
render();
Result
Console

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 Real Complexity

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 Θ(n+m)\Theta(n+m) time and Θ(n+m)\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)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 rr, the right boundary moves one step to the right. Since rr starts at 0 and can move at most n+mn + m times total, at most n+mn + m extension comparisons happen across the entire run.
  2. All other comparisons are lookups into previously computed Z-values — O(1)O(1) each. They do not extend rr, so they are bounded by the number of positions, also n+mn + m.

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

Comparison with alternatives:

Method Time Space Notes
Naive O(n⋅m)O(n \cdot m) O(1)O(1) Slow on repetitive text
Rabin-Karp O(n+m)O(n+m) avg O(1)O(1) Hash collisions require fallback
KMP O(n+m)O(n+m) O(m)O(m) Failure function, same complexity
Z-algorithm O(n+m)O(n+m) O(n+m)O(n+m) Explicit prefix lengths, clean proof
Aho-Corasick O(n+Σ⋅m)O(n+\Sigma \cdot m) O(Σ⋅m)O(\Sigma \cdot m) Multiple patterns simultaneously

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.

Where It Matters

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)O(n + m) guarantee.

Conclusion

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)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/z-algorithm/Content licensed under CC BY-NC 4.0.