Z-algorithm — Z-array construction, O(n+m): Worked examples

This page is the drill hall. The parent note built the machine; here we feed it every kind of input and turn the crank by hand — every case, every degenerate string, and a real-world pattern hunt.

If a word or symbol below feels unfamiliar, it was defined in the parent — but we re-anchor the essentials so you can start from line one.

Recall Three words you must keep in your head

Z-array — for each starting index $i$ , the number $Z [i]$ = how many letters starting at $i$ match the very start (the prefix) of the string. If $s = aab...$ and starting at $i$ you read aab, that's a 3-letter match, so $Z [i] = 3$ .
Prefix — the letters at the front of the string: a, then aa, then aab, ... The prefix is our "secret code" we keep comparing against.
Z-box $[l, r]$ — the rightmost stretch we already proved is a photocopy of the prefix: $s [l .. r] = s [0.. r - l]$ . l = left edge, r = right edge (both are indices). We carry this box along and reuse it.

The scenario matrix

Strings don't have "quadrants", but the Z-algorithm has exactly six behavioural cells an input can land in. Every worked example below is tagged with the cell(s) it exercises. Together they cover the whole machine.

Cell	Name	The situation	What the code does
C1	Outside the box ( $i > r$ )	No stored info at $i$	Compare from scratch; maybe open a new box
C2	Inside, mirror fits (B1)	$Z [i - l] < r - i + 1$	Copy $Z [i - l]$ free, no compare, no box change
C3	Inside, mirror hits edge (B2)	$Z [i - l] \geq r - i + 1$	Copy up to edge, then march past $r$ , grow box
C4	Degenerate all-same	$s = aaaa$	The $O (n^{2})$ -trap that the box defuses to $O (n)$
C5	Degenerate all-different	$s = abcd$	Every $Z [i] = 0$ ; box never opens past width 1
C6	Real / exam	Pattern search, empty & length-1 edges	Glue-with-separator trick, limiting inputs

Zero/limiting inputs live inside C4–C6: empty string ( $n = 0$ ), one-char string ( $n = 1$ ), and the separator boundary all appear below.

Example 1 — the clean warm-up (hits C1)

Worked example

$s = abcababc$ , compute the whole Z-array Indices $0..7$ : a b c a b a b c.

Forecast: guess $Z [3]$ before reading on. Starting at 3 we read abab...; the prefix is abc.... How far do they agree?

$Z [0] = 0$ by convention (the whole string trivially equals itself; we never use it). Why this step? It seeds $l = r = 0$ so the very first real index is treated as "outside the box".
$i = 1$ : $i = 1 > r = 0$ → C1, compare from scratch. s[0]=a vs s[1]=b ✗ → $Z [1] = 0$ . No box. Why this step? Outside any box we have zero information, so we must genuinely look at the characters.
$i = 2$ : $2 > 0$ → C1. s[0]=a vs s[2]=c ✗ → $Z [2] = 0$ .
$i = 3$ : $3 > 0$ → C1. s[0]=a=s[3]=a ✓, s[1]=b=s[4]=b ✓, s[2]=c vs s[5]=a ✗ → $Z [3] = 2$ . New box: $l = 3, r = 3 + 2 - 1 = 4$ . Why this step? The match reached further right than $r = 0$ , so per the last if we open a box $[3, 4]$ to reuse later.
$i = 4$ : $4 \leq r = 4$ → inside. Mirror $i^{'} = 4 - 3 = 1$ , $Z [1] = 0$ , edge $r - i + 1 = 1$ , $min (1, 0) = 0$ . march: s[0]=a vs s[4]=b ✗ → $Z [4] = 0$ . C2 (mirror 0 fit inside).
$i = 5$ : $5 > r = 4$ → C1. s[0]=a=s[5]=a✓, s[1]=b=s[6]=b✓, s[2]=c=s[7]=c✓, then index 8 doesn't exist → $Z [5] = 3$ . Box $l = 5, r = 7$ .
$i = 6$ : $6 \leq 7$ → inside. Mirror $i^{'} = 1$ , $Z [1] = 0$ , edge $= 2$ , $min (2, 0) = 0$ . march: s[0]=a vs s[6]=b ✗ → $Z [6] = 0$ . C2.
$i = 7$ : $7 \leq 7$ → inside. Mirror $i^{'} = 2$ , $Z [2] = 0$ , edge $= 1$ , $min = 0$ . march: s[0]=a vs s[7]=c ✗ → $Z [7] = 0$ . C2.

Answer: $Z = [0, 0, 0, 2, 0, 3, 0, 0]$ .

Verify: Position 3 reads abab vs prefix abca → agree on ab=2. ✔ Position 5 reads abc vs prefix abc → 3. ✔ The forecast: $Z [3] = 2$ .

Example 2 — mirror fits inside (hits C2, the free copy)

Worked example

$s = aabaacaab$ , find $Z [4]$ and $Z [7]$ cheaply Indices $0..8$ : a a b a a c a a b.

Forecast: at $i = 7$ we'll be deep inside a box. Do you think the code touches any characters at all?

Build up to the box. $i = 1$ (C1): a=a, a≠b → $Z [1] = 1$ , box $[1, 1]$ .
$i = 2$ (C1): a≠b → $Z [2] = 0$ .
$i = 3$ (C1, since $3 > r = 1$ ): a=a,a=a,b=b? s[2]=b vs s[5]=c ✗ → $Z [3] = 2$ , box $l = 3, r = 4$ . Why this step? This opens the box we exploit next.
$i = 4$ : $4 \leq r = 4$ → inside. Mirror $i^{'} = 4 - 3 = 1$ , $Z [1] = 1$ , edge $r - i + 1 = 1$ , $min (1, 1) = 1$ . Here the mirror value equals the edge, so march checks: s[1]=a vs s[5]=c ✗ → stays $Z [4] = 1$ . (Borderline C2/C3 — the min capped it, march verified one step, no growth.)
Continue: $i = 5$ (C1): a≠c → $Z [5] = 0$ . $i = 6$ (C1): a=a,a=a,b=b → matches aab, end → $Z [6] = 3$ , box $l = 6, r = 8$ .
$i = 7$ : $7 \leq r = 8$ → inside. Mirror $i^{'} = 7 - 6 = 1$ , $Z [1] = 1$ , edge $r - i + 1 = 2$ . Since $1 < 2$ , the mirror fits strictly inside → pure C2: $Z [7] = 1$ , and the march loop's first test would still be inside so it stops immediately after confirming — but conceptually we copied for free. Why this step? The mismatch that ended the mirror's match (at $s [2] = b$ vs $s [1] = a$ ... captured as $Z [1] = 1$ ) lives inside the box, so it is guaranteed to repeat at $i = 7$ . No new comparison needed.
$i = 8$ : $8 \leq 8$ → inside. Mirror $i^{'} = 2$ , $Z [2] = 0$ , edge $= 1$ , $min = 0$ . march: s[0]=a vs s[8]=b ✗ → $Z [8] = 0$ .

Answer: $Z = [0, 1, 0, 2, 1, 0, 3, 1, 0]$ ; the highlight is $Z [7] = 1$ obtained without a fresh character comparison.

Verify: starting at 7 read ab; prefix aa; a=a✓, b≠a✗ → length 1. ✔ Matches the free copy.

Example 3 — mirror hits the edge, must march (hits C3)

Worked example

$s = aaabaaa$ , watch the box grow past $r$ Indices $0..6$ : a a a b a a a.

Forecast: at $i = 5$ the mirror will want to reach beyond the box. Will $Z [5]$ be bigger than its mirror value?

$i = 1$ (C1): a=a,a=a,a? s[2]=a vs s[3]=b? wait — compare prefix vs shifted: s[0]=a=s[1]=a✓, s[1]=a=s[2]=a✓, s[2]=a vs s[3]=b✗ → $Z [1] = 2$ , box $l = 1, r = 2$ .
$i = 2$ : $2 \leq r = 2$ → inside. Mirror $i^{'} = 1$ , $Z [1] = 2$ , edge $r - i + 1 = 1$ . $min (1, 2) = 1$ → the mirror exceeds the edge, so we cap at 1 and march: s[1]=a vs s[3]=b✗ → $Z [2] = 1$ . C3-lite (capped, marched, no growth here).
$i = 3$ (C1, $3 > r = 2$ ): s[0]=a vs s[3]=b✗ → $Z [3] = 0$ .
$i = 4$ (C1): a=a,a=a,a? s[2]=a vs s[6]=a✓, then index 7 gone → matches aaa=3 → $Z [4] = 3$ , box $l = 4, r = 6$ . Why this step? Opens the box that the next index will lean on.
$i = 5$ : $5 \leq r = 6$ → inside. Mirror $i^{'} = 5 - 4 = 1$ , $Z [1] = 2$ , edge $r - i + 1 = 2$ . $min (2, 2) = 2$ → mirror reaches the edge → true C3: start marching at $k = 2$ : index $i + Z [i] = 5 + 2 = 7$ is out of bounds → stop → $Z [5] = 2$ . Box would be $5 + 2 - 1 = 6 = r$ , not further right, so no box update (this is the "don't shrink $r$ " rule).
$i = 6$ : $6 \leq r = 6$ → inside. Mirror $i^{'} = 2$ , $Z [2] = 1$ , edge $= 1$ . $min (1, 1) = 1$ . march: index $6 + 1 = 7$ out of bounds → $Z [6] = 1$ .

Answer: $Z = [0, 2, 1, 0, 3, 2, 1]$ .

Verify: start at 5 read aa (indices 5,6); prefix aa; both match, string ends → length 2. ✔ The forecast: $Z [5] = 2$ equals its mirror here because the string ran out, but the mechanism was "march past the edge".

Example 4 — the $O (n^{2})$ -trap defused (hits C4, degenerate all-same)

Figure — Z-algorithm — Z-array construction, O(n+m)

Worked example

$s = aaaaaa$ ( $n = 6$ ) — the worst case for naive, easy for Z Forecast: naive comparison here would do $5 + 4 + 3 + 2 + 1$ comparisons. Guess how many the Z-box version does.

$i = 1$ (C1): march all the way — a=a five times until index 6 out of bounds → $Z [1] = 5$ , box $l = 1, r = 5$ . That's 5 comparisons, pushing $r$ from $0$ to $5$ . Why this step? This is the only place we pay: each successful while step moved $r$ one step right.
$i = 2$ : $2 \leq 5$ → inside. Mirror $i^{'} = 1$ , $Z [1] = 5$ , edge $r - i + 1 = 4$ . $min (4, 5) = 4$ . march at $k = 4$ : index $2 + 4 = 6$ out of bounds → $Z [2] = 4$ . Zero extra comparisons (the min already capped it; the one march test just fails at the boundary). No box growth.
$i = 3$ : inside, mirror $Z [1]$ via... mirror $i^{'} = 2$ , $Z [2] = 4$ , edge $= 3$ , $min = 3$ → $Z [3] = 3$ . Free.
$i = 4$ : mirror $i^{'} = 3$ , $Z [3] = 3$ , edge $= 2$ , $min = 2$ → $Z [4] = 2$ . Free.
$i = 5$ : mirror $i^{'} = 4$ , $Z [4] = 2$ , edge $= 1$ , $min = 1$ → $Z [5] = 1$ . Free.

Answer: $Z = [0, 5, 4, 3, 2, 1]$ . Cost: the entire array cost 5 successful marches + a handful of boundary checks, i.e. $O (n)$ — not $O (n^{2})$ .

Verify: for aaaaaa, $Z [i] = n - i = 6 - i$ for $i \geq 1$ : $Z [1] = 5, \dots, Z [5] = 1$ . ✔ Look at the figure: the red box opened once at $i = 1$ and every later index just read its mirror off the prefix, no repeat scanning (the dotted arrows).

Example 5 — nothing ever matches (hits C5, degenerate all-different)

Worked example

$s = abcdef$ and the empty/one-char edges Forecast: what is $Z [i]$ for every $i \geq 1$ here? And what does the algorithm do when $n = 0$ or $n = 1$ ?

$n = 0$ (empty string): the for i in 1..n-1 loop never runs; $Z$ is empty. Why? No positions exist — a legitimate limiting input the code handles without special-casing.
$n = 1$ ( $s = a$ ): loop range $1..0$ is empty, $Z = [0]$ . Only the convention entry survives.
$n = 6$ , all distinct: for each $i \geq 1$ , C1 fires and the first comparison s[0] vs s[i] fails (all letters differ) → $Z [i] = 0$ . The box never opens beyond width 1, so we're always in C1. Why this step? With no repeated prefix character, there is never a stored match to reuse — the box stays empty. This is C5.

Answer: $n = 6$ → $Z = [0, 0, 0, 0, 0, 0]$ ; $n = 1$ → $Z = [0]$ ; $n = 0$ → $Z = []$ .

Verify: count of nonzero entries for abcdef is $0$ . ✔ Length checks: $∣ Z ∣ = n$ in all three cases ( $6, 1, 0$ ). ✔

Example 6 — real-world pattern hunt (hits C6, the separator trick)

Worked example Find every occurrence of

$p = aba$ in $t = ababa$ This is the flagship application: KMP and String Hashing solve the same task, but Z does it with one array.

Forecast: how many times does aba occur in ababa? Overlapping counts. Guess before computing.

Glue with a separator: $S = p + # + t = aba#ababa$ , length $m + 1 + n = 3 + 1 + 5 = 9$ . Indices $0..8$ : a b a # a b a b a. Why this step? The # (guaranteed absent from $p$ and $t$ ) blocks matches from bleeding across the boundary; then "pattern occurs" becomes " $Z [i] = m$ ".
Compute $Z$ over $S$ :
- $i = 1$ : a≠b → $Z [1] = 0$ .
- $i = 2$ : a=a, then s[1]=b vs s[3]=#✗ → $Z [2] = 1$ . box $[2, 2]$ .
- $i = 3$ : #≠a → $Z [3] = 0$ .
- $i = 4$ : a=a,b=b,a=a, then s[3]=# vs s[7]=b✗ → $Z [4] = 3$ . box $[4, 6]$ .
- $i = 5$ : inside, mirror $i^{'} = 1$ , $Z [1] = 0$ , edge $= 2$ , $min = 0$ ; march avsb✗ → $Z [5] = 0$ .
- $i = 6$ : inside, mirror $i^{'} = 2$ , $Z [2] = 1$ , edge $= 1$ , $min = 1$ ; march s[1]=b vs s[7]=b✓, s[2]=a vs s[8]=a✓, index 9 gone → $Z [6] = 3$ . box $[6, 8]$ .
- $i = 7$ : inside, mirror $i^{'} = 1$ , $Z [1] = 0$ ,edge $= 2$ , $min = 0$ ; avsb✗ → $Z [7] = 0$ .
- $i = 8$ : inside, mirror $i^{'} = 2$ , $Z [2] = 1$ ,edge $= 1$ , $min = 1$ ; index $8 + 1 = 9$ gone → $Z [8] = 1$ .
Read off matches: $Z [i] = m = 3$ at $i = 4$ and $i = 6$ . Convert to text position: $i - (m + 1) = i - 4$ . So $t$ -positions $0$ and $2$ . Why this step? Subtracting $m + 1$ removes the pattern-plus-separator offset, mapping back into $t$ .

Answer: aba occurs in ababa at positions 0 and 2 (they overlap on the middle a). Two matches.

Verify: ababa[0:3]=aba ✔, ababa[2:5]=aba ✔. Count = 2. The figure shows the glued string with the two full-length Z-hits highlighted in teal.

Example 7 — exam twist: partial vs full, and a false-positive trap (C6)

Worked example Why the separator matters:

$p = ab$ , $t = xaby$ Forecast: if a careless student glued without # as $S = p + t = abxaby$ , could a false match appear?

Correct glue: $S = ab#xaby$ (length 7), indices a b # x a b y.
- $i = 4$ : a=a,b=b,s[2]=# vs s[6]=y✗ → $Z [4] = 2 = m$ . Match! Text position $= 4 - (m + 1) = 4 - 3 = 1$ .
- all other $i$ : $Z [i] < 2$ . Why this step? The single hit at $i = 4$ gives text position 1, which is where ab sits in xaby.
The trap (no separator): $S = abxaby$ . Now suppose the last char of $p$ could accidentally chain with the first of $t$ . With # this is impossible because # breaks any prefix match at the boundary — you can never get $Z [i] \geq m$ starting inside $t$ unless a genuine full copy of $p$ sits there. Why this step? The separator guarantees $Z [i] = m$ only for real, self-contained occurrences.

Answer: ab occurs in xaby at position 1, exactly one match.

Verify: xaby[1:3]=ab ✔. Number of positions $i$ with $Z [i] = 2$ in ab#xaby is 1. ✔

See also: Amortized Analysis (why the marching total is $O (n)$ ), Manacher's Algorithm (the same box trick for palindromes), Suffix Array and Suffix Automaton (heavier structures for the same string questions).