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

Position $4$ starts the run $s[4]s[5]s[6]=\text{aba}$. The prefix starts $s[0]s[1]s[2]=\text{aba}$.

• Compare $s[0]=\text{a}$ vs $s[4]=\text{a}$ ✓ (length so far 1)
• Compare $s[1]=\text{b}$ vs $s[5]=\text{b}$ ✓ (length 2)
• Compare $s[2]=\text{a}$ vs $s[6]=\text{a}$ ✓ (length 3)
• Next would be $s[7]$, which doesn't exist → stop.

So $==Z[4]=3==$. The match stopped because we ran off the end of the string, not because of a mismatch.

Every suffix of aaaaa is itself a run of a's equal to the prefix, but capped by how many characters remain.

$Z[1]$: from index 1 there are 4 characters left, all a, all match the prefix → $4$. Each subsequent index has one fewer character remaining. Answer: $Z=[-,4,3,2,1]$.

Start $l=r=0$, $Z[0]=0$.

• $i=1$: $i>r=0$ → Case A. Compare $s[0]=\text{a}$ vs $s[1]=\text{b}$ ✗ → $Z[1]=0$. No box.
• $i=2$: $i>r=0$ → Case A. ababab vs prefix ababab matches all 6 remaining → $Z[2]=6$. Box $l=2,r=7$.
• $i=3$: $i=3\le r=7$ → Case B. Mirror $i^{\prime }=1$, $Z[1]=0$, cap $r-i+1=5$, $\min (5,0)=0$; while: $s[0]=\text{a}$ vs $s[3]=\text{b}$ ✗ → $Z[3]=0$.
• $i=4$: $\le r$ → Case B. $i^{\prime }=2$, $Z[2]=6$, cap $r-i+1=4$, $\min (4,6)=4$; while: $s[4]=\text{a}$? we test $s[Z]=s[4]=\text{a}$ vs $s[i+Z]=s[8]$ — out of range → stop. $Z[4]=4$. New box? $i+Z-1=7$, not $>r=7$, so no update.
• $i=5$: $\le r$ → Case B. $i^{\prime }=3$, $Z[3]=0$, cap $=3$, $\min =0$; while $s[0]=\text{a}$ vs $s[5]=\text{b}$ ✗ → $Z[5]=0$.
• $i=6$: $\le r$ → Case B. $i^{\prime }=4$, $Z[4]=4$, cap $r-i+1=2$, $\min (2,4)=2$; while $s[2]=\text{a}$ vs $s[8]$ out of range → stop. $Z[6]=2$.
• $i=7$: $\le r$ → Case B. $i^{\prime }=5$, $Z[5]=0$, cap $=1$, $\min =0$; while $s[0]=\text{a}$ vs $s[7]=\text{b}$ ✗ → $Z[7]=0$.

$Z=[-,0,6,0,4,0,2,0]$.

$S=\text{aab\#aababaab}$, length $m+1+n=3+1+8=12$. Indices:

We need $Z[i]=3$. Checking the text region ($i\ge 4$):

• $i=4$: aab vs prefix aab ✓✓✓, then $S[3]=\text{\#}$ vs $S[7]=\text{a}$ ✗ → $Z[4]=3$. Hit.
• $i=9$: aab vs aab ✓✓✓, then off end → $Z[9]=3$. Hit.
• All other positions give $Z<3$.

Convert with position $=i-(m+1)=i-4$:

• $i=4\Rightarrow t$-position $0$.
• $i=9\Rightarrow t$-position $5$.

So $p=\text{aab}$ occurs at $t$-positions $==\{0,5\}==$. Check: $t[\mathrm{0..2}]=\text{aab}$ ✓, $t[\mathrm{5..7}]=\text{aab}$ ✓.

At $i=4$: cap $=\min (r-i+1,Z[i-l])=\min (4,6)=4$, so the loop entered with $Z[4]=4$. It then tested s[4] == s[8] — but $i+Z=4+4=8=n$ is out of range, so the while condition i+Z[i] < n is false immediately. Zero character comparisons. The value 4 was copied from the mirror knowledge, verified for free.

At $i=2$ (Case A): we started at $Z[2]=0$ and had to compare from scratch: 6 successful matches then off the end → 6 character comparisons. This is the "real work" that pushed $r$ from $0$ to $7$.

Key insight: the free copy at $i=4$ is exactly the reuse the box buys us — the mirror at $i^{\prime }=2$ already paid for those matches.

At the time we process these, the box is $l=3,r=5$.

• $i=4$: mirror $i^{\prime }=1$, $Z[1]=1$. Box edge distance $r-i+1=5-4+1=2$. Is $Z[i^{\prime }]<r-i+1$? $1<2$ ✓ → B1. The mirror's match (length 1) and its terminating mismatch both lie strictly inside the box, so $Z[4]=1$ is copied with no comparison.
• $i=5$: mirror $i^{\prime }=2$, $Z[2]=0$. Edge distance $r-i+1=1$. Is $0<1$? Yes → this is B1 as well ($Z[i^{\prime }]$ fits). We copy $Z[5]=0$; the while tests $s[0]$ vs $s[5]$ once and fails, adding nothing.

Neither is a true B2 here, because no mirror value reached the box boundary. A B2 example: in abababab at $i=4$, $Z[i^{\prime }]=6\ge$ edge $4$, so it hit the cap — that's the B2 shape (we relied on the min to stop us claiming unverified territory).

The prefix of length $k$ occurs starting at position $i$ iff $Z[i]\ge k$ (a match at least $k$ long begins there). We also always count position $0$ itself.

Build $Z$ for ababa:

• $i=1$: $s[0]=\text{a}$ vs $s[1]=\text{b}$ ✗ → $Z[1]=0$.
• $i=2$: aba vs aba → 3 matches, off end → $Z[2]=3$. Box $l=2,r=4$.
• $i=3$: $\le r$, mirror $i^{\prime }=1$, $Z[1]=0$, cap $=2$, $\min =0$; $s[0]=\text{a}$ vs $s[3]=\text{b}$ ✗ → $Z[3]=0$.
• $i=4$: $\le r$, mirror $i^{\prime }=2$, $Z[2]=3$, cap $r-i+1=1$, $\min (1,3)=1$; while $s[1]=\text{b}$ vs $s[5]$ out of range → $Z[4]=1$.

$Z=[-,0,3,0,1]$. Count positions (including 0) with $Z[i]\ge 2$: position $0$ (prefix itself), $i=2$ ($Z=3\ge 2$). That's $==2==$ occurrences of ab. Check by eye: ababa → ab at indices $0$ and $2$. ✔

We need positions where the match runs exactly to the end: $i+Z[i]=n=10$.

Compute the relevant Z-values by hand:

• $i=5$: run abcab vs prefix abcab → matches 5 (s[5..9]=abcab, prefix abcab), then off end → $Z[5]=5$, and $5+5=10$ ✓. Border length $5$.
• Any longer? A border of length $6$ would need $Z[4]=6$ with $4+6=10$; but $s[4]=\text{b}\ne s[0]=\text{a}$ → $Z[4]=0$. No.

Longest proper border length $===5==$ (abcab). Check: prefix abcab = suffix abcab of abcababcab. ✔ This is exactly the information the KMP failure function stores; Z gives an alternative route to it.

$r$ changes only inside the box-update line, which fires iff $i+Z[i]-1>r$, and sets $r\leftarrow i+Z[i]-1$. By its own guard, the new $r$ is strictly greater than the old $r$. No other line touches $r$. Therefore $r$ is (weakly) non-decreasing — in fact strictly increasing whenever it changes at all. ∎

Bound on while work. Each successful while iteration matches a character at position $i+Z[i]$ that was beyond the old $r$ (positions $\le r$ were already known, so extension only happens past $r$), and then $r$ advances to cover it. Since $r$ starts at $0$, strictly increases on each such success, and is $\le n-1$ forever, there are at most $n$ successful while iterations across the entire run. Each $i$ also has at most one failing while test (the mismatch that ends its loop), giving $\le n$ additional constant-cost tests. Total: $O(n)$. Combined with the $O(m)$ concatenation for pattern matching → $==O(n+m)==$.

• (a) empty string $n=0$: the array is empty, $Z=[]$. No positions to process; the loop for i in 1..n-1 runs zero times. Valid.
• (b) x, $n=1$: $Z=[-]$ (only $Z[0]$, unused). The loop starts at $i=1>n-1=0$, so it never runs. There is no proper suffix to match.
• (c) yy, $n=2$: $i=1$, Case A, $s[0]=\text{y}$ vs $s[1]=\text{y}$ ✓, then off end → $Z[1]=1$. So $Z=[-,1]$.
• (d) a^k (letter repeated $k$ times): by the L1.2 pattern, $Z[i]=k-i$ for $i\ge 1$. Formula: $==Z[i]=k-i==$. This is the worst case for the naive algorithm (${\sum }_i(k-i)=\Theta (k^2)$) yet the box-based algorithm still runs in $O(k)$: the box jumps to cover the whole tail at $i=1$, and every later $i$ is a free B1 copy.

• Feeling strong? Compare Z with the KMP failure function — they compute closely related border information by different mechanics.
• For matching under hashing instead of prefix matching, see String Hashing.
• Palindrome-flavored cousin of this reuse trick: Manacher's Algorithm.
• Heavier full-text index structures: Suffix Array, Suffix Automaton.
• The linear-time proof style generalizes: Amortized Analysis.
• Hinglish walkthrough of the core: 3.8.04 Z-algorithm — Z-array construction, O(n+m) (Hinglish).