Z-algorithm — Z-array construction, O(n+m): Visual walkthrough

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

Neeche sab kuch ek hi running string par kaam karta hai. Chaliye use abhi fix karte hain taaki har figure ek hi language bole.

Step 1 — $Z [i]$ kya sawaal poochta hai?

KYA. Koi bhi starting position $i$ lo. String ke beginning ki ek copy slide karo taaki uska pehla letter position $i$ ke upar baithe. Ab right walk karo, letter-by-letter compare karo, aur count karo ki pehle disagreement se pehle kitne letters match hue. Woh count $Z [i]$ hai.

$Z [i] = how many letters we counted length of the longest run where start of string s [0], s [1], \dots = starting at i s [i], s [i + 1], \dots$

$s [0], s [1], \dots$ — prefix, front se padha hua.
$s [i], s [i + 1], \dots$ — substring $i$ se start hoti hai, wahan se padha hua jahan humne apni copy rakhi.
"longest run" — hum pehle mismatch par ruk jaate hain (ya string ke end par).

KYUN. Yeh ek number secretly pattern matching ko power karta hai (pattern ko text ke aage glue karo; ek $Z$ -value jo pattern ki length ke barabar ho = ek match). Lekin pehle humein ise padhna aana chahiye.

PICTURE. Neeche overlaid ruler $Z [3] = 3$ dikhata hai: teen green ticks, phir string khatam.

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

Recall Apni reading check karo

$Z [3] = 3$ kyun hai aur $4$ kyun nahi? ::: After matching aab (3 letters) we reach position $3 + 3 = 6$ , which is off the end of the string — there is no letter to compare, so we stop at $3$ .

Step 2 — Naive method, aur yeh kyun dukh deta hai

KYA. Obvious plan: har starting position $i$ ke liye, ruler dobara plant karo aur scratch se count karo. Koi memory nahi, koi cleverness nahi.

YEH SLOW KYUN HAI. Cruel input $s = aaaaaa$ consider karo. Position $1$ par $5$ letters match hote hain, position $2$ par $4$ match hote hain, aur aise chalte rahta hai. Tum almost poori tail ko har baar re-scan karte ho:

$total comparisons \approx (n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2} = O (n^{2})$

$n$ — string ki length.
Sum $(n - 1) + (n - 2) + \dots$ — har position par kaam, jod ke.
$O (n^{2})$ — length ke square ki tarah badhta hai: string double karo, kaam chaar guna ho jaata hai.

Yahi woh quadratic wall hai jo KMP failure function aur String Hashing todne ke liye banaye gaye the. Hum $O (n)$ chahte hain: kaam jo sirf string ke proportionally badhta ho.

PICTURE. Re-scanned regions ki staircase — dekho kitna red overlap waste re-work hai.

Step 3 — Ek idea: string apne aap ko photocopy karta hai

KYA. Maan lo kisi pehle wali position par humne ek lamba match discover kiya — maan lo position $l$ se start hoke prefix se kaafi der tak match hua, position $r$ par khatam hua. Toh letters $s [l .. r]$ ka poora stretch letter-for-letter identical hai prefix $s [0.. r - l]$ ke. Hum $[l, r]$ ko ek Z-box kehte hain: ek window jo hum already prove kar chuke hain string ke front ke barabar hai.

$the window we found s [l .. r] = the prefix, same length s [0.. r - l]$

$l$ — window ka left edge (jahan prefix ki matched copy shuru hoti hai).
$r$ — right edge (last position jo humne verify ki).
$r - l$ — window ki length minus one, isliye prefix piece $s [0.. r - l]$ ki length $s [l .. r]$ ke barabar hai.

YEH GOLD KYUN HAI. Is window ke andar string apne hi beginning ki ek photocopy hai. Isliye position $i$ window ke andar wala letter guaranteed equal hai us letter ke jo uski mirror position par front ke paas hai. Hum woh answers chura sakte hain jo hum already compute kar chuke hain — free mein, zero new comparisons ke saath.

PICTURE. Window $[l, r]$ (mint) seedha identical prefix (lavender) ke neeche rakhi; dashed lines har position ko uske mirror se connect karti hain.

Step 4 — Mirror position, exactly defined

KYA. Ek position $i$ lo jo box ke andar baithe ( $l \leq i \leq r$ ). Prefix mein uska mirror hai:

$i^{'} = i - l$

$i$ — jahan hum abhi khade hain, window ke andar.
$l$ — window ka left edge.
$i - l$ — $i$ left edge se kitna dur hai; wahi distance string ke front se us mirror $i^{'}$ par land karta hai.

KYUN. Kyunki window prefix ki photocopy hai, $i$ par letter $i^{'}$ par letter ke barabar hai, aur isse bhi zyada: jo bhi match length humne pehle $i^{'}$ par nikali thi (value $Z [i^{'}]$ ) $i$ par copy ho jaani chahiye — jab tak woh match window ke andar rahti hai.

PICTURE. Mint box ke andar position $i$ ; arrow $i^{'} = i - l$ tak lavender prefix mein fold back karta hai. $i^{'}$ par chota match-run $i$ par copy hone ke liye ready dikhaya gaya hai.

Step 5 — Case B1: mirror ka match box ke andar fit ho jaata hai

KYA. Hum box ke andar hain aur do lengths compare karte hain: mirror ne kitna match kiya, $Z [i^{'}]$ , versus box edge tak kitni jagah bachi hai, $r - i + 1$ .

$room to edge = r - i + 1$

$r$ — window ka right edge.
$i$ — current position.
$r - i + 1$ — $i$ se $r$ tak positions ka count including $r$ (woh "+1" $i$ ko bhi include karta hai).

Agar $Z [i^{'}] < r - i + 1$ hai, toh mirror ka poora match — including woh mismatch jo use end kiya — window ke andar hai. Kyunki window ek exact copy hai, wahi match aur wahi terminating mismatch $i$ par repeat hota hai:

$Z [i] = Z [i^{'}] (no comparisons at all)$

KOI COMPARISON KYUN NAHI. Woh letter jo mirror ke match ko todta tha window ke andar hai, isliye woh ek known, copied letter hai. Woh guaranteed hai ki $i$ par match ko same spot par todega. Dobara check karna redundant hoga.

PICTURE. Mirror ka chota match (green) apne red mismatch ke saath, dono box ke andar safely, $i$ par verbatim copy kiya hua.

Step 6 — Case B2: mirror ka match box edge se bahar nikal jaata hai

KYA. Ab $Z [i^{'}] \geq r - i + 1$ : mirror kam se kam box boundary tak match kiya. Edge $r$ tak hum copy par trust kar sakte hain — lekin $r$ ke baad koi photocopy nahi hai, isliye hume haath se compare karna hoga:

$Z [i] = trusted, box se (r - i + 1) + r ke baad verify karna hoga (comparing se mile extra matches)$

$(r - i + 1)$ — woh portion jo hume free milta hai, edge tak.
extra term — new letters jo hum actually compare karte hain, position $r + 1$ se start karke, right walk karte hue jab tak mismatch na ho.

$r$ ke baad jo bhi discover hota hai woh box ko extend karta hai: hum $l = i$ aur $r = i + Z [i] - 1$ set karte hain, kyunki ab hum ek longer prefix-match jaante hain jo aur aage right tak pahuncha.

KYUN CAP MATTER KARTA HAI. $Z [i^{'}]$ ko blindly copy karna yahan $r$ ke baad matches claim kar deta — jo kabhi check nahi hue — ek jhooth. Hum sirf edge tak trust karte hain, phir verify karte hain.

PICTURE. Mirror ka match box edge se aage nikal jaata hai; green up to $r$ , phir $r$ ke baad ek "?" zone jahan fresh comparisons shuru hoti hain (aur $r$ ko aage push karti hain).

Step 7 — Degenerate cases (koi gap mat chhodna)

KYA. Teen boundary situations jo picture ko cover karni chahiye:

$i > r$ — har box ke bahar. Koi photocopy exist nahi karti. Fresh start: $Z [i] = 0$ , phir position $0$ se compare karo. Agar kuch match hota hai, naya box kholo.
Box ke andar $Z [i^{'}] = 0$ . Mirror kabhi match nahi hua; $min (r - i + 1, 0) = 0$ , aur $i$ par pehla comparison bhi likely fail hoga. Kuch gain nahi, kuch break nahi.
Match string ke bilkul end tak pahunch jaata hai. while isliye rukta hai kyunki $i + Z [i] = n$ (compare karne ke liye koi letter nahi), mismatch ki wajah se nahi. aab mein position $2$ string ke tail par exactly aisa hi hai.

YEH MATTER KYUN KARTA HAI. Amortized $O (n)$ argument is baat par rely karta hai ki $r$ sirf badhta hi hai. Isliye parent note ki teesri galti — box ko tab update karna jab naya match $r$ ke past nahi pahunchta — forbidden hai: yeh $r$ ko shrink hone deta aur linearity khatam kar deta.

PICTURE. Teen mini-panels: (1) $r$ ke past fresh start, (2) zero mirror, (3) run-off-the-end. Har ek dikhata hai ki box edge $r$ kabhi peeche nahi jaata.

Step 8 — $s = aabaab$ par Full trace

KYA. Dekho $[l, r]$ kaise right ki taraf creep karta hai jab hum $Z$ ko left to right fill karte hain.

$i$	case	$min (r - i + 1, Z [i^{'}])$	`while` ke baad	box $[l, r]$
1	$i > r$	—	$Z [1] = 1$	$[1, 1]$
2	$i > r$	—	$Z [2] = 0$	unchanged
3	$i > r$	—	$Z [3] = 3$	$[3, 5]$
4	$i \leq r$ , $i^{'} = 1$	$min (2, 1) = 1$	$Z [4] = 1$ (B1)	unchanged
5	$i \leq r$ , $i^{'} = 2$	$min (1, 0) = 0$	$Z [5] = 0$	unchanged

Result: $Z = [-, 1, 0, 3, 1, 0]$ .

YAHAN LINEAR KYUN HAI. Real character comparisons sirf tab hue jab $r$ $0$ se $5$ tak push hua. Positions $4$ aur $5$ ne kuch nahi pay kiya — unhone copy kiya. Box ek baar forward sweep kiya; kabhi retreat nahi kiya.

PICTURE. Saato chah positions par moving box, green "copied" positions ko red "compared" walo se alag dikhaya hua.

Ek-picture summary

Is page par sab kuch ek single diagram mein collapse ho jaata hai: prefix, rightmost box, mirror fold, aur box edge par branching hote do cases.

Recall Feynman: poora walkthrough retell karo

String ke pehle kuch letters ko ek stamp ki tarah socho. Tum woh stamp string ke saath press karte ho aur count karte ho ki kitne letters line up hote hain pehle ek galat hone se — woh count $Z [i]$ hai (Step 1). Yeh har jagah scratch se karna boring inputs jaise aaaa par thaka dene wala hai (Step 2). Lekin har lamba match jo tum dhundho woh actually string ke opening ki ek photocopy hai (Step 3), aur us photocopy ke andar koi bhi spot ka ek twin front ke paas hota hai — uska mirror (Step 4). Agar twin ka match photocopy ke andar completely fit ho jaata hai, toh bas twin ka answer copy karo, koi kaam nahi (Step 5, B1). Agar twin ka match photocopy ke right edge se spill ho jaata hai, toh edge tak trust karo aur baaki haath se compare karo, jo photocopy ko aur right extend karta hai (Step 6, B2). Jab tum photocopy se bilkul bahar ho, ya twin ne kuch nahi dhundha, ya string ka end aa gaya — unhe seedha handle karo, aur crucially right edge $r$ sirf aage hi badhti hai (Step 7). Ise aabaab par trace karo aur dekho ki box exactly ek baar right creep karta hai, real comparisons sirf grow karte waqt karta hai (Step 8). Forward-only motion hi poori wajah hai ki total kaam linear hai.