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

3.8.4 · D3 · Coding › String Algorithms › Z-algorithm — Z-array construction, O(n+m)

Yeh page drill hall hai. Parent note ne machine banayi thi; yahan hum us machine mein har tarah ka input daalte hain aur haath se crank ghumate hain — har case, har degenerate string, aur ek real-world pattern hunt.

Agar koi word ya symbol neeche unfamiliar lage, toh woh parent mein define kiya gaya tha — lekin hum essentials ko yahan re-anchor karte hain taaki tum line one se shuru kar sako.

Recall Teen words jo tumhe hamesha yaad rakhne chahiye

Z-array — har starting index $i$ ke liye, number $Z [i]$ = kitne letters $i$ se shuru hokar string ke bilkul shuru (yaani prefix) se match karte hain. Agar $s = aab...$ hai aur $i$ se shuru karke tum aab padhte ho, toh woh 3-letter match hai, isliye $Z [i] = 3$ .
Prefix — string ke saamne wale letters: a, phir aa, phir aab, ... Prefix woh "secret code" hai jisse hum baar baar compare karte rehte hain.
Z-box $[l, r]$ — woh rightmost stretch jo hum pehle se prove kar chuke hain ki prefix ki photocopy hai: $s [l .. r] = s [0.. r - l]$ . l = left edge, r = right edge (dono indices hain). Hum is box ko saath lekar chalte hain aur reuse karte hain.

Scenario matrix

Strings ke "quadrants" nahi hote, lekin Z-algorithm ke exactly chhe behavioural cells hain jisme ek input ja sakta hai. Neeche har worked example un cell(s) ke saath tagged hai jo woh exercise karta hai. Milake woh poori machine cover karte hain.

Cell	Naam	Situation	Code kya karta hai
C1	Box ke bahar ( $i > r$ )	$i$ par koi stored info nahi	Scratch se compare karo; ho sakta hai naya box kholo
C2	Andar, mirror fit ho jaye (B1)	$Z [i - l] < r - i + 1$	$Z [i - l]$ free mein copy karo, koi compare nahi, koi box change nahi
C3	Andar, mirror edge ko hit kare (B2)	$Z [i - l] \geq r - i + 1$	Edge tak copy karo, phir $r$ ke aage march karo, box badhao
C4	Degenerate all-same	$s = aaaa$	Woh $O (n^{2})$ -trap jo box $O (n)$ mein defuse karta hai
C5	Degenerate all-different	$s = abcd$	Har $Z [i] = 0$ ; box kabhi width 1 se zyada nahi khulta
C6	Real / exam	Pattern search, empty aur length-1 edges	Glue-with-separator trick, limiting inputs

Zero/limiting inputs C4–C6 ke andar hain: empty string ( $n = 0$ ), one-char string ( $n = 1$ ), aur separator boundary — yeh sab neeche aate hain.

Example 1 — clean warm-up (C1 ko hit karta hai)

Worked example

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

Forecast: aage padhne se pehle $Z [3]$ guess karo. Index 3 se shuru karke hum abab... padhte hain; prefix hai abc.... Kitni dur agree karte hain?

$Z [0] = 0$ convention ke hisaab se (poori string trivially khud se equal hai; hum ise kabhi use nahi karte). Yeh step kyun? Yeh $l = r = 0$ seed karta hai taaki pehla real index "box ke bahar" treat ho.
$i = 1$ : $i = 1 > r = 0$ → C1, scratch se compare karo. s[0]=a vs s[1]=b ✗ → $Z [1] = 0$ . Koi box nahi. Yeh step kyun? Kisi bhi box ke bahar hume zero information hai, toh genuinely characters dekhne padte hain.
$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$ . Naya box: $l = 3, r = 3 + 2 - 1 = 4$ . Yeh step kyun? Match $r = 0$ se aage right tak pahuncha, toh last if ke hisaab se hum box $[3, 4]$ kholte hain baad mein reuse karne ke liye.
$i = 4$ : $4 \leq r = 4$ → andar. 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, andar fit).
$i = 5$ : $5 > r = 4$ → C1. s[0]=a=s[5]=a✓, s[1]=b=s[6]=b✓, s[2]=c=s[7]=c✓, phir index 8 exist nahi karta → $Z [5] = 3$ . Box $l = 5, r = 7$ .
$i = 6$ : $6 \leq 7$ → andar. 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$ → andar. 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 pe abab padhte hain vs prefix abca → ab=2 par agree. ✔ Position 5 pe abc padhte hain vs prefix abc → 3. ✔ Forecast: $Z [3] = 2$ .

Example 2 — mirror andar fit hota hai (C2 ko hit karta hai, free copy)

Worked example

$s = aabaacaab$ , $Z [4]$ aur $Z [7]$ saste mein nikalo Indices $0..8$ : a a b a a c a a b.

Forecast: $i = 7$ par hum ek box ke andar kafi gehre honge. Kya tumhare hisaab se code wahan koi bhi character touch karta hai?

Box tak build up karo. $i = 1$ (C1): a=a, a≠b → $Z [1] = 1$ , box $[1, 1]$ .
$i = 2$ (C1): a≠b → $Z [2] = 0$ .
$i = 3$ (C1, kyunki $3 > r = 1$ ): a=a,a=a,b=b? s[2]=b vs s[5]=c ✗ → $Z [3] = 2$ , box $l = 3, r = 4$ . Yeh step kyun? Yeh woh box kholta hai jise hum aage exploit karenge.
$i = 4$ : $4 \leq r = 4$ → andar. Mirror $i^{'} = 4 - 3 = 1$ , $Z [1] = 1$ , edge $r - i + 1 = 1$ , $min (1, 1) = 1$ . Yahan mirror value edge ke equal hai, toh march check karta hai: s[1]=a vs s[5]=c ✗ → $Z [4] = 1$ rehta hai. (Borderline C2/C3 — min ne cap kiya, march ne ek step verify kiya, koi growth nahi.)
Continue: $i = 5$ (C1): a≠c → $Z [5] = 0$ . $i = 6$ (C1): a=a,a=a,b=b → aab match karta hai, khatam → $Z [6] = 3$ , box $l = 6, r = 8$ .
$i = 7$ : $7 \leq r = 8$ → andar. Mirror $i^{'} = 7 - 6 = 1$ , $Z [1] = 1$ , edge $r - i + 1 = 2$ . Kyunki $1 < 2$ , mirror strictly andar fit hota hai → pure C2: $Z [7] = 1$ , aur march loop ka pehla test abhi bhi andar hoga toh immediately ruk jayega — lekin conceptually hum ne free mein copy kiya. Yeh step kyun? Woh mismatch jo mirror ke match ko khatam karta tha (at $s [2] = b$ vs $s [1] = a$ ... $Z [1] = 1$ ke roop mein captured) box ke andar hai, toh guaranteed hai ki woh $i = 7$ par repeat hoga. Koi nayi comparison ki zaroorat nahi.
$i = 8$ : $8 \leq 8$ → andar. 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]$ ; highlight yeh hai ki $Z [7] = 1$ bina kisi fresh character comparison ke mila.

Verify: index 7 se shuru karke ab padhte hain; prefix aa; a=a✓, b≠a✗ → length 1. ✔ Free copy se match karta hai.

Example 3 — mirror edge ko hit karta hai, march karna padta hai (C3 ko hit karta hai)

Worked example

$s = aaabaaa$ , dekho box $r$ ke aage grow karta hai Indices $0..6$ : a a a b a a a.

Forecast: $i = 5$ par mirror box ke aage jaana chahega. Kya $Z [5]$ apni mirror value se bada hoga?

$i = 1$ (C1): a=a,a=a,a? s[2]=a vs s[3]=b? ruko — prefix vs shifted compare karo: 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$ → andar. Mirror $i^{'} = 1$ , $Z [1] = 2$ , edge $r - i + 1 = 1$ . $min (1, 2) = 1$ → mirror edge se zyada hai, toh hum 1 par cap karte hain aur march karte hain: s[1]=a vs s[3]=b✗ → $Z [2] = 1$ . C3-lite (capped, marched, yahan koi growth nahi).
$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✓, phir index 7 gone → aaa=3 match karta hai → $Z [4] = 3$ , box $l = 4, r = 6$ . Yeh step kyun? Woh box kholta hai jis par next index lean karega.
$i = 5$ : $5 \leq r = 6$ → andar. Mirror $i^{'} = 5 - 4 = 1$ , $Z [1] = 2$ , edge $r - i + 1 = 2$ . $min (2, 2) = 2$ → mirror edge tak pahunchta hai → true C3: $k = 2$ par march shuru karo: index $i + Z [i] = 5 + 2 = 7$ out of bounds hai → ruko → $Z [5] = 2$ . Box hoga $5 + 2 - 1 = 6 = r$ , further right nahi, toh koi box update nahi (yeh "don't shrink $r$ " rule hai).
$i = 6$ : $6 \leq r = 6$ → andar. 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: index 5 se shuru karke aa padhte hain (indices 5,6); prefix aa; dono match karte hain, string khatam → length 2. ✔ Forecast: $Z [5] = 2$ yahan apni mirror value ke equal hai kyunki string khatam ho gayi, lekin mechanism tha "march past the edge".

Example 4 — $O (n^{2})$ -trap defused (C4 ko hit karta hai, degenerate all-same)

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

Worked example

$s = aaaaaa$ ( $n = 6$ ) — naive ke liye worst case, Z ke liye easy Forecast: naive comparison yahan $5 + 4 + 3 + 2 + 1$ comparisons karti. Andaaza lagao ki Z-box version kitni karta hai.

$i = 1$ (C1): poora march karo — a=a paanch baar jab tak index 6 out of bounds na ho jaye → $Z [1] = 5$ , box $l = 1, r = 5$ . Yeh hain 5 comparisons, $r$ ko $0$ se $5$ tak push karte hue. Yeh step kyun? Sirf yahan hum pay karte hain: har successful while step ne $r$ ko ek step right move kiya.
$i = 2$ : $2 \leq 5$ → andar. Mirror $i^{'} = 1$ , $Z [1] = 5$ , edge $r - i + 1 = 4$ . $min (4, 5) = 4$ . $k = 4$ par march: index $2 + 4 = 6$ out of bounds → $Z [2] = 4$ . Zero extra comparisons (min ne already cap kar diya tha; ek march test bas boundary par fail hota hai). Koi box growth nahi.
$i = 3$ : andar, 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: poore array mein sirf 5 successful marches + thodi boundary checks lagi, yaani $O (n)$ — $O (n^{2})$ nahi.

Verify: aaaaaa ke liye, $Z [i] = n - i = 6 - i$ for $i \geq 1$ : $Z [1] = 5, \dots, Z [5] = 1$ . ✔ Figure dekho: red box sirf ek baar $i = 1$ par khula aur baad ke har index ne apna mirror prefix se free mein padha, koi repeat scanning nahi (dotted arrows).

Example 5 — kabhi kuch match nahi karta (C5 ko hit karta hai, degenerate all-different)

Worked example

$s = abcdef$ aur empty/one-char edges Forecast: yahan har $i \geq 1$ ke liye $Z [i]$ kya hoga? Aur algorithm kya karta hai jab $n = 0$ ya $n = 1$ ho?

$n = 0$ (empty string): for i in 1..n-1 loop kabhi nahi chalta; $Z$ empty hai. Kyun? Koi position exist nahi karti — ek legitimate limiting input jise code bina special-casing ke handle karta hai.
$n = 1$ ( $s = a$ ): loop range $1..0$ empty hai, $Z = [0]$ . Sirf convention entry bachti hai.
$n = 6$ , sab alag: har $i \geq 1$ ke liye, C1 fire karta hai aur pehla comparison s[0] vs s[i] fail ho jaata hai (sab letters alag hain) → $Z [i] = 0$ . Box kabhi width 1 se zyada nahi khulta, toh hum hamesha C1 mein hain. Yeh step kyun? Koi repeated prefix character na hone par, store kiya hua match kabhi nahi hota reuse ke liye — box khali rehta hai. Yeh C5 hai.

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

Verify: abcdef mein nonzero entries ki count $0$ hai. ✔ Length checks: $∣ Z ∣ = n$ teeno cases mein ( $6, 1, 0$ ). ✔

Example 6 — real-world pattern hunt (C6 ko hit karta hai, separator trick)

Worked example

$p = aba$ ki har occurrence $t = ababa$ mein dhundho Yeh flagship application hai: KMP aur String Hashing same task solve karte hain, lekin Z ek hi array se karta hai.

Forecast: ababa mein aba kitni baar aata hai? Overlapping count karo. Compute karne se pehle guess karo.

Separator se glue karo: $S = p + # + t = aba#ababa$ , length $m + 1 + n = 3 + 1 + 5 = 9$ . Indices $0..8$ : a b a # a b a b a. Yeh step kyun? # (jo guaranteed $p$ aur $t$ mein absent hai) matches ko boundary ke paas se bleeding se rokta hai; phir "pattern occurs" ka matlab ban jaata hai " $Z [i] = m$ ".
$S$ par $Z$ compute karo:
- $i = 1$ : a≠b → $Z [1] = 0$ .
- $i = 2$ : a=a, phir 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, phir s[3]=# vs s[7]=b✗ → $Z [4] = 3$ . box $[4, 6]$ .
- $i = 5$ : andar, mirror $i^{'} = 1$ , $Z [1] = 0$ , edge $= 2$ , $min = 0$ ; march avsb✗ → $Z [5] = 0$ .
- $i = 6$ : andar, 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$ : andar, mirror $i^{'} = 1$ , $Z [1] = 0$ ,edge $= 2$ , $min = 0$ ; avsb✗ → $Z [7] = 0$ .
- $i = 8$ : andar, mirror $i^{'} = 2$ , $Z [2] = 1$ ,edge $= 1$ , $min = 1$ ; index $8 + 1 = 9$ gone → $Z [8] = 1$ .
Matches read off karo: $Z [i] = m = 3$ at $i = 4$ aur $i = 6$ . Text position mein convert karo: $i - (m + 1) = i - 4$ . Toh $t$ -positions $0$ aur $2$ . Yeh step kyun? $m + 1$ subtract karne se pattern-plus-separator offset hat jaata hai, $t$ mein wapas map ho jaate hain.

Answer: aba, ababa mein positions 0 aur 2 par aata hai (woh beech ke a par overlap karte hain). Do matches.

Verify: ababa[0:3]=aba ✔, ababa[2:5]=aba ✔. Count = 2. Figure glued string ko two full-length Z-hits ke saath teal mein highlight karke dikhata hai.

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

Worked example Separator kyun matter karta hai:

$p = ab$ , $t = xaby$ Forecast: agar ek careless student ne bina # ke $S = p + t = abxaby$ ki tarah glue kiya, toh kya false match aa sakta hai?

Sahi 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$ .
- baaki sab $i$ : $Z [i] < 2$ . Yeh step kyun? $i = 4$ par single hit text position 1 deta hai, jo wahi hai jahan ab xaby mein baitha hai.
Trap (koi separator nahi): $S = abxaby$ . Ab maan lo $p$ ka last char accidentally $t$ ke first char ke saath chain kar le. # ke saath yeh impossible hai kyunki # boundary par kisi bhi prefix match ko tod deta hai — tum kabhi $Z [i] \geq m$ nahi pa sakte $t$ ke andar se shuru hone par jab tak wahan $p$ ki ek genuine puri copy na ho. Yeh step kyun? Separator guarantee karta hai ki $Z [i] = m$ sirf real, self-contained occurrences ke liye ho.

Answer: ab, xaby mein position 1 par aata hai, exactly ek match.

Verify: xaby[1:3]=ab ✔. ab#xaby mein $Z [i] = 2$ wale positions ki count 1 hai. ✔

See also: Amortized Analysis (kyun marching total $O (n)$ hai), Manacher's Algorithm (palindromes ke liye same box trick), Suffix Array aur Suffix Automaton (same string questions ke liye heavier structures).