The Z-Algorithm

The 10-second versionCopy Anchor Link

The Z-array of a string records, for every position i, the length of the longest substring starting at i that matches a prefix of the whole string — call it z[i]. You can compute all of it in O(n) by remembering the rightmost prefix-match you've seen so far and copying answers from the "mirror" position when you're inside it. To search for a pattern in a text, glue them together as pattern + "$" + text and read off every position where z[i] equals the pattern's length. Same O(n + m) as KMP, but the whole algorithm is one pass with one clever window.

Why this existedCopy Anchor Link

By the late 1970s, KMP had already made pattern matching linear. So the Z-algorithm isn't a breakthrough in speed — it's a breakthrough in framing. KMP answers a very specific question ("how far do I shift the pattern after a mismatch?") and its bookkeeping is tied to that one job. The Z-array answers a broader question — "how much does each suffix agree with the prefix?" — and that single object happens to solve a whole family of string problems: periodicities, counting distinct substrings, and building suffix arrays, not just search.

• 1977 — KMP makes single-pattern search linear with its prefix function.
• 1987 — Rabin-Karp adds a randomized, hashing-based alternative.
• 1997 — Dan Gusfield formalizes and popularizes the Z-algorithm in Algorithms on Strings, Trees, and Sequences, presenting the "Z-box" as a clean, self-contained linear scan. The idea echoes earlier prefix-match work; the book is what put the name and shape in everyone's hands.
• 2000s onward — z-functions become a standard tool in contest code, suffix-array construction, and text-processing libraries.

Why it mattered: KMP tells you when to shift; Z tells you how much every position matches the start. That rephrasing turns a single-purpose matcher into a reusable primitive.

Inside the inventor's headCopy Anchor Link

Start naive. To fill the Z-array, at each position i just compare the suffix starting at i against the prefix from index 0, character by character, and stop at the first mismatch:

// Naive z-array: compare each suffix to the prefix head-on — O(n^2)function naiveZ(s) {  const n = s.length, z = new Array(n).fill(0);  for (let i = 1; i < n; i++) {    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;  }  return z;}// Linear z-array: reuse the rightmost known prefix-match boxfunction zFunction(s);

The naive scan is O(n²) on strings like aaaa…a, where every suffix matches the prefix for a long stretch. The pivot is to notice that these stretches overlap, and overlapping prefix matches tell you about each other. If you already found that the string equals its prefix on the interval l … r, then any position inside that interval can borrow its answer from the corresponding position near the start.

That last line is the payoff: the "extend" step only ever advances the right end r, and r never moves backwards, so the total extension work across the whole scan is O(n).

The final approachCopy Anchor Link

The Z-arrayCopy Anchor Link

For a string s of length n, define z[i] as the length of the longest common prefix of s and the suffix s[i..]. By convention z[0] = n (the whole string trivially matches).

The algorithmCopy Anchor Link

Keep [l, r], the interval of the rightmost prefix match found so far — that is, s[l..r] equals s[0..r-l]. When i lands inside it, the mirror position i - l already tells you a lower bound on z[i]; you copy it, capped so it can't run past r, then try to extend.

The invariantsCopy Anchor Link

1. Box meaning. s[l..r] == s[0..r-l], and r is the furthest right index any prefix match has reached.
2. Mirror bound. For i inside the box, z[i] ≥ min(r - i, z[i - l]) — the substring at i matches the prefix at least that far, by transitivity through the box.
3. Monotone r. Every character comparison either starts beyond r (and pushes it right) or immediately stops. So r only advances, and the total comparisons are O(n).

A worked traceCopy Anchor Link

s = a a b c a a b:

Result: z = [7, 1, 0, 0, 3, 1, 0]. Positions 5 and 6 never re-compared most characters — they borrowed from their mirrors.

Pattern matching with a sentinelCopy Anchor Link

Build s = pattern + "$" + text, where $ is a character that appears in neither. Any position i in the text part where z[i] equals the pattern length means the pattern occurs there — because the only way a suffix matches pattern $ for that long is a real occurrence.

It in codeCopy Anchor Link

// z[i] = length of the longest substring at i that matches a prefix of sfunction zFunction(s) {  const n = s.length;  const z = new Array(n).fill(0);  if (n === 0) return z;  z[0] = n;  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 zSearch(text, pat) {  const m = pat.length;  const s = pat + "\u0001" + text;      // sentinel absent from text and pattern  const z = zFunction(s);  for (let i = m + 1; i < s.length; i++)    if (z[i] === m) return i - m - 1;  return -1;}

ComplexityCopy Anchor Link

Contrast with KMPCopy Anchor Link

Both are Θ(n + m); the difference is what they preprocess.

They encode very similar information — KMP's π[i] and the Z-array of the pattern are two views of the same "prefix meets suffix" structure — but the Z framing generalizes more naturally to problems that aren't about search at all.

Finding every occurrenceCopy Anchor Link

Because a match is just z[i] == m, listing all matches is a scan, not a loop-with-fallbacks:

function zFindAll(text, pat) {  const m = pat.length;  const s = pat + "\u0001" + text;  const z = zFunction(s);  const hits = [];  for (let i = m + 1; i < s.length; i++)    if (z[i] === m) hits.push(i - m - 1);  return hits;}

Where you meet it todayCopy Anchor Link

• Suffix arrays and LCP. Z-functions are a common subroutine for computing longest common prefixes, which in turn drive suffix-array construction and string-index building.
• Periodicity and borders. Whether a string is a repetition of a shorter block, and where its borders are, fall straight out of the Z-array — used in compression and pattern analysis.
• Bioinformatics and text search. Matching a short motif against a long reference, or checking whether two reads share a prefix, are one-scan Z jobs.
• Competitive programming. Anything phrased as "how much does this suffix share with the prefix?" is a Z-algorithm problem waiting to be noticed.

function smallestPeriod(s) {  const n = s.length;  if (n === 0) return 0;  const z = zFunction(s);  for (let p = 1; p < n; p++)    if (n % p === 0 && z[p] === n - p) return p;  // whole string tiles in p  return n;}

RecapCopy Anchor Link

• The Z-array stores, at each i, how long the substring starting at i matches the prefix — computed in O(n) using a single sliding "z-box".
• You only ever copy from the mirror i - l and then extend; since the box's right end never moves backwards, the total work is linear.
• Pattern matching is pattern + "$" + text: every z[i] == m in the text part is a match, for O(n + m) overall.
• It reaches the same Θ(n + m) as KMP but preprocesses the combined string, making it a natural primitive for prefix/suffix and periodicity problems, not just search.

Next up: Strongly Connected Components — we leave strings behind and return to graphs, where we condense cycles into a DAG.