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

3.8.4 · Coding › String Algorithms

Z-array HAI KYA?

Concretely $Z [i] = max {k : s [0.. k - 1] = s [i .. i + k - 1]}$ .

Naive version $O (n^{2})$ kyun lagta hai — aur fix kaise karein?

Naive: har $i$ ke liye, $s [i + k]$ ko $s [k]$ se compare karo jab tak mismatch na ho. Worst case aaaa...a → har $i$ end tak scan karta hai → $\sum i = O (n^{2})$ .

Ise BUILD kaise karein — scratch se derivation

Hum ek window $[l, r]$ maintain karte hain = ab tak mila sabse rightmost segment jo prefix se match karta hai (shuru mein $l = r = 0$ ).

Har $i$ ke liye $1$ se $n - 1$ tak, do cases:

Case A — $i > r$ (hum kisi bhi known box ke bahar hain). Hamare paas koi information nahi. Scratch se compare karo: $Z [i] = max {k : s [k] = s [i + k]}$ $k = 0$ se shuru karo. Agar $Z [i] > 0$ hai, naya box set karo $l = i, r = i + Z [i] - 1$ .

Case B — $i \leq r$ (hum box ke andar hain). $i^{'} = i - l$ ko prefix mein mirror position maano. Hum $Z [i^{'}]$ jaante hain. Do sub-cases:

B1: $Z [i^{'}] < r - i + 1$ . Mirror ka match poora box ke andar fit ho jaata hai. Kyunki box ke andar $s$ bilkul prefix ke barabar hai, position $i$ par match identical hai: $Z [i] = Z [i^{'}] (no comparisons, no box update)$ Comparison kyun nahi? Kyunki jo mismatch mirror ke match ko khatam karta hai woh box ke andar hi hai, toh guaranteed hai ki $i$ par bhi wahi repeat hoga.
B2: $Z [i^{'}] \geq r - i + 1$ . Mirror ka match box boundary tak pahunch jaata hai; $r$ se aage koi guarantee nahi, isliye $k = r - i + 1$ se manually compare karna padega: $Z [i] = (r - i + 1) + (extra matches found by comparing s [k] vs s [i + k])$ Phir box update karo $l = i, r = i + Z [i] - 1$ .

Formula Poora algorithm

l = r = 0
Z[0] = 0
for i in 1 .. n-1:
    if i <= r:                    # Case B: inside box
        Z[i] = min(r - i + 1, Z[i - l])
    while i + Z[i] < n and s[Z[i]] == s[i + Z[i]]:   # extend (B2 / Case A)
        Z[i] += 1
    if i + Z[i] - 1 > r:          # new rightmost box
        l = i
        r = i + Z[i] - 1

Akela while loop elegantly Case A (initial $Z [i] = 0$ ) aur B2 dono handle karta hai. min B1 ko handle karta hai box edge par cap karke, taaki jab mirror box ke andar fit ho jaaye toh while zero extra kaam kare.

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

Total cost $O (n + m)$ kyun hai?

Pattern matching application

Pattern $p$ (length $m$ ) ko text $t$ (length $n$ ) mein dhundhne ke liye: string banao $S = p + # + t (# \in / p, t)$ $S$ (length $m + 1 + n$ ) par $Z$ compute karo. Jahan bhi $Z [i] = m$ ho, wahan pattern $t$ mein position $i - (m + 1)$ par milta hai. Total cost $O (n + m)$ .

Common mistakes

Recall Feynman: 12-saal ke bachche ko samjhao

Socho kisi word ke pehle kuch letters tumhara "secret code" hain. Tum baaki word mein chalo aur har jagah poocho: "Yahan se shuru karke, kitne letters word ke shuru se match karte hain?" Slow tarika hai ki har baar zero se re-check karo. Clever trick yeh hai: agar tumne pehle ek lamba chunk match kiya tha, toh woh chunk shuruat ka ek photocopy hai — toh us chunk ke andar kisi jagah ka behavior bilkul wahi hoga jo shuruat ke matching jagah jaisa hai. Tum bas woh answer dekh lo jo pehle se likha hua hai, dobara count karne ki zarurat nahi. Naya counting sirf tab karo jab photocopied chunk ki edge ke bahar jao — aur kyunki woh edge sirf aage hi jaati hai, zyada kaam kabhi nahi hoga.

Flashcards

Z[i] kya represent karta hai?

Index

i

se shuru hone wale substring ki length jo

s

ka prefix bhi hai, aur jo sabse lamba ho.

Naive Z computation

O (n^{2})

kyun hai?

"aaa...a" jaisi strings ke liye har starting index end tak re-scan karta hai, jo

O (n^{2})

comparisons tak add up hoti hain.

Z-box [l,r] kya hai?

Sabse rightmost (largest

r

) interval jo prefix se match karna already known hai:

s [l .. r] = s [0.. r - l]

Case B (

i \leq r

) mein mirror index kya hai?

i^{'} = i - l

; prefix ke andar corresponding position.

Box ke andar

Z [i - l]

copy kyun kar sakte hain bina compare kiye?

[l, r]

ke andar string prefix ke equal hai, isliye

s [i] = s [i - l]

; mirror ka match (aur uska terminating mismatch) exactly repeat hota hai — agar woh box ke andar rahe. :::

min (r - i + 1, Z [i - l])

kisse bachata hai?

r

se aage aisi matches claim karne se jo kabhi verify nahi hui; yeh trust ko box boundary par cap karta hai.

Box kab update karte hain?

Sirf jab

i + Z [i] - 1 > r

ho, yaani naya match current box se aage right mein jaaye.

Total cost

O (n)

kyun hai?

Inner while ki har iteration

r

ko 1 se badhati hai;

r

sirf badhta hai aur

\leq n - 1

hai, isliye total extensions

\leq n

hain.

Z se pattern matching kaise karein?

S = pattern + # + text

banao,

Z

compute karo; jahan

Z [i] = m

(pattern length) ho woh matches hain.

Separator '#' dono strings mein absent kyun hona chahiye?

Warna Z-match boundary ke paas ja sakta hai aur false occurrence report kar sakta hai.

Connections

String Hashing — alternate $O (n)$ substring-match tool; Z hash collisions se bachata hai.
KMP failure function — prefix-match info bhi compute karta hai; Z aur prefix-function aapas mein convert ho sakte hain.
Suffix Array / Suffix Automaton — repeated queries ke liye heavier structures.
Amortized Analysis — " $r$ sirf badhta hai" wala argument ek potential-function classic hai.
Manacher's Algorithm — palindromes ke liye same "symmetric/mirror box reuse" trick.