↩ back to Exact Match

Z-Algorithm

KMP precomputes a table from the pattern alone, then consults it during a separate pass over the text. The Z-algorithm takes a structurally different approach: glue the pattern and the text into a single string, build one array over that whole string, and read every match straight off it — no separate search phase, no fallback table consulted mid-scan. For any string S, define Z[i] as the length of the longest prefix of S that also occurs starting at position i. Build S = pattern + separator + text, and since S starts with the pattern, Z[i] ≥ |pattern| at some position means a full copy of the pattern starts right there — that comparison against the array is the entire search, once the array exists. Built naively, that array would cost as much as the naive substring search it replaces; built with the same "reuse what's already proven, don't recompute it" idea behind KMP's own failure function — applied here to the whole concatenation instead of pattern-only fallback links — it costs only O(n+m). On the exact same worst-case input as this site's KMP page (nineteen As then a B, searched for nine As then a B), naive character-by-character search needs 110 comparisons; the Z-algorithm needs 57 (checked below, not just claimed).

Try it

Enter a text and a pattern (up to 30 and 12 characters; neither may contain # — the demo uses it internally as the separator between pattern and text). Step through building the Z-array over S = pattern + '#' + text, left to right. At each index the array either copies a value for free from an already-verified window (no character comparisons spent) or extends it by comparing characters directly — watch the running comparison count. The instant an index inside the text portion reaches Z[i] ≥ |pattern|, that position is a confirmed match; it's flagged immediately and highlighted in the plain text row below, with no separate search step.

Why it works

Z[i] is defined by comparing S against itself, shifted: it's the longest common prefix of S and the suffix of S starting at i. Computed naively, position i costs up to n-i character comparisons, and nothing stops every position from hitting close to that bound on a repetitive string (verified in Pitfalls below) — O(n²) overall.

The optimization keeps a running window [l, r) — the rightmost extent any earlier index's match has reached, established while processing index l and extending to r = l + Z[l]. Its meaning: every character of S from position l up to r is already known to equal the corresponding prefix character (S[l..r) mirrors S[0..r-l), character for character — that's exactly what made Z[l] reach r). So for a new index i inside that window, S[i..r) is guaranteed to equal S[i-l..r-l) — a position already fully computed, since i-l < i. That hands over a free lower bound, min(r-i, Z[i-l]), without checking a single new character. Two cases follow: if Z[i-l] is strictly less than r-i, the mirrored match ends inside the verified window, where it's known to be exactly right — copy it and move on, zero comparisons. If Z[i-l] ≥ r-i, the mirror only guarantees a match up to the window's edge; what happens at and past r has never actually been compared, so the algorithm starts comparing for real from position r-i onward, extending the window as far as it verifiably goes. Either way Z[i] is finalized before moving to i+1, and only genuinely new characters — ones the window has never covered before, since the window only ever grows — receive an explicit comparison. That's the same accounting argument that gives KMP its O(n) bound, applied here to the shared concatenation as a whole instead of pattern-only fallback pointers.

Reading a match off the finished array is the flip side of the same definition: the first |pattern| characters of S are the pattern (that's how S was built), so Z[i] ≥ |pattern| at some position literally means "the characters starting at position i match the first |pattern| characters of S" — which is exactly the definition of "the pattern occurs at that position." No separate search state machine is needed, because the Z-array's own definition already is the answer to "does the pattern occur here": construction and search happen in the same pass.

Reference implementation

This is the exact scheme the demo above steps through:

function zArray(s) {
  const n = s.length;
  const 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]);   // free lower bound from the mirrored position
    }
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) {
      z[i]++;                             // only ever compares characters never seen before
    }
    if (i + z[i] > r) {
      l = i;
      r = i + z[i];                       // window only ever grows
    }
  }
  return z;
}

function zSearch(text, pat) {
  const m = pat.length;
  const s = pat + '#' + text;   // separator must not appear in pat or text
  const z = zArray(s);
  const matches = [];
  for (let i = m + 1; i < s.length; i++) {
    if (z[i] >= m) matches.push(i - m - 1);   // Z[i] >= m means pat occurs here
  }
  return matches;
}

Pitfalls

The copied estimate must be capped at the window's edge — skip the cap and the array can hold a value that's not just wrong but literally impossible. On S = "BABBABBAB" (length 9), the correct construction reaches index i=6 with a window [l=3, r=9) established from Z[3]=6. The capped copy is min(r-i, Z[i-l]) = min(9-6, Z[3]) = min(3, 6) = 3, and the extend loop has nothing left to check (i + 3 = 9 is already past the end of the string) — final Z[6] = 3, correct: only three characters ("BAB", indices 6–8) even remain to compare. Drop the cap and copy Z[i-l] outright — a tempting "simplification" since it looks like it's just reusing more information — and index 6 gets Z[6] = 6, a value that would require six characters to still exist from position 6 onward when only three do. It's silently wrong rather than a crash, because the copied value mirrors a match that was verified starting at a different alignment (position 0), and nothing beyond the window's own edge has ever actually been compared for this alignment. Checked directly against the traced construction on this exact string, not reasoned about abstractly.

Skipping the [l, r) window entirely still finds the right answer — it just costs quadratically more on repetitive input. Recomputing every Z[i] from scratch, comparing S against itself fresh at each position with no reused work, produces an identical array (checked: byte-for-byte identical output across every position tried), just slower. On thirty repeated As, naive per-position construction costs 435 character comparisons; the windowed version costs 29 — measured directly, not estimated. That's the same O(n²)-vs-O(n) gap KMP's own naive-vs-KMP comparison count highlights, landing here on the Z-array's construction rather than a separate search pass, because for this algorithm construction and search are the same walk. On this page's own default example (concatenating the intro's nine As-plus-B pattern with its nineteen-As-plus-B text), naive construction costs 201 comparisons against the windowed version's 57 — the same worst case the intro's 110-vs-57 search comparison already draws on, viewed from the construction side instead of the search side.

This is the same "reuse instead of recompute" principle behind KMP's failure function, applied to a different structure entirely — one array over pattern-plus-text together, rather than a table over the pattern alone. Its worst-case guarantee is unconditionally O(n+m), like KMP's, and unlike Rabin-Karp's average-case-fast, hash-collision-checking approach. Like KMP and Boyer-Moore, it's built around finding one pattern; matching many patterns against the same text at once is Aho-Corasick's job, not this one's.

Complexity

Time: O(n), where n = |pattern| + 1 + |text| is the length of the concatenated string — one left-to-right pass builds the whole Z-array. The bound holds the same way KMP's does: the window's right edge r only ever moves forward, so across the entire run an explicit character comparison either extends r by one (bounded by n total extensions) or fails once and stops (bounded by n, one failure per index that reaches the extend loop) — the windowed copy step itself costs no comparisons at all. Reading matches off the finished array is an additional O(n) scan. Space: O(n) for the Z-array and the concatenated string — more than KMP's O(m), since this array holds one entry per character of pattern-plus-text rather than one entry per character of the pattern alone.

Every algorithm on this site so far pays its cost once per search, scanning the text (or, here, pattern-plus-text) fresh each time. Suffix Array pays a similar cost only once, total — sorting the text's own suffixes up front — so that any number of later pattern queries each cost a pair of binary searches instead of another full pass. See Choosing an Exact-Match String Matcher for how this unconditional guarantee compares to the other nine exact-match entries.