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

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

Quick symbol refresh taaki pehli line ka matlab samajh aaye:

$s$ hamari string hai, length $n$ , positions numbered $0, 1, \dots, n - 1$ .
$Z [i]$ = kitne characters, position $i$ se start karke, $s$ ke beginning (prefix) se match karte hain.
$[l, r]$ = rightmost Z-box: wo interval jo hum already prove kar chuke hain ki prefix ke barabar hai, aur jiska right end $r$ sabse bada hai.
$i^{'} = i - l$ = $i$ ka mirror: wo jagah $s$ ke shuru ke paas jo $i$ ki photocopy hai, jab $i$ box ke andar hota hai.

True or false — justify

Poori string apna prefix khud hai, isliye

Z [0]

n

ke barabar hona chahiye.

Technically sach hai — position

0

par substring length

n

ke pure prefix se match karti hai. Lekin hum convention se

Z [0] = 0

set karte hain kyunki wahan

n

use karne se box logic aur pattern-matching scan index

0

par ek jhootha "match" report karta; hume us value ki zaroorat kabhi nahi padti.

Agar

s

aaaa

hai, toh

Z [1] = 3

Sach. Position

1

se shuru karke hum

aaa

padhte hain, jo prefix

aaa

se teeno characters ke liye match karta hai jab tak string khatam ho jaaye, isliye

Z [1] = 3

Z-array ki har entry

Z [i] \leq n - i

satisfy karti hai.

Sach. Position

i

se shuru hone wala match

i

se end tak bache characters se zyada use nahi kar sakta, aur exactly

n - i

hi bache hote hain.

Box ke andar equality

s [i] = s [i - l]

sirf shayad true hai, isliye hume phir bhi verify karna chahiye.

Galat.

[l, r]

ke andar string provably prefix ke barabar hai, isliye

s [i] = s [i - l]

ek proven fact hai, guess nahi. Use dobara verify karna exactly wahi kaam waste karta hai jise skip karne ke liye algorithm design hua tha.

Agar do positions

i

aur

j

ka mirror value same ho

Z [i^{'}] = Z [j^{'}]

, toh unka

Z

-value bhi same hoga.

Galat. Copy tabhi trusted hoti hai jab mirror ka match box ke andar rahe; agar unme se koi boundary

r

tak pahunch jaaye toh hume comparison se extend karna padega, jo possibly bada answer deta hai.

Box

[l, r]

backward move ho sakta hai (

l

decrease ho sakta hai) jab

i

badhta hai.

Galat. Hum box tab hi update karte hain jab koi naya match current

r

se aage jaata hai, isliye

r

kabhi decrease nahi hota;

l

naye starting index par jump karta hai lekin right end sirf aage hi badhta hai.

Length

n

ki string ka Z-array build karne mein while loop mein kabhi bhi

n

se zyada character comparisons nahi hote.

Sach. Har successful while comparison

r

ko ek aage push karta hai;

r

0

se at most

n - 1

tak jaata hai aur kabhi peeche nahi aata, jo saari extensions ko total

O (n)

mein bound karta hai.

Tum Z-array ko left to right ki jagah right to left compute kar sakte ho aur same complexity milegi.

Spirit mein galat — poora method pehle se jaani hui matches pe rely karta hai left ki taraf (chhote indices), taaki box fill ho, isliye left to right process karna essential hai; right-to-left pass mein koi reused information nahi hogi.

Spot the error

i \leq r

ke liye,

Z [i] = Z [i - l]

directly set karo aur aage badho."

Error cap skip karna hai. Agar

Z [i - l]

box edge

r

se aage jaata hai, toh tum

r

ke baad matches claim kar rahe ho jo kabhi check nahi hue; tumhe

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

use karna chahiye aur phir while ko edge ke baad kuch bhi verify karne do.

Z [i]

compute karne ke baad, box ko fresh rakhne ke liye hamesha

l = i, r = i + Z [i] - 1

set karo."

Error unconditional updating hai. Agar

i + Z [i] - 1 \leq r

hai toh yeh

r

ko shrink kar deta hai, "

r

sirf badhta hai" invariant aur amortized

O (n)

proof ko destroy kar deta hai. Sirf tab update karo jab naya match aur aage jaaye.

"Case B jahan

Z [i - l] \geq r - i + 1

ka matlab answer exactly

r - i + 1

hai."

Error boundary par rukna hai. Edge tak pahunchna sirf

r

tak match guarantee karta hai;

r

ke baad aur zyada matching characters ho sakte hain, isliye tumhe

k = r - i + 1

se aage compare karna jaari rakhna chahiye.

"Pattern

p

ko text

t

mein dhundhne ke liye, bas

p + t

concatenate karo aur

Z [i] = m

dekhte raho."

Error missing separator hai. Bina sentinel ke, ek match

p

–

t

boundary ke upar ja sakta hai aur

p

ke characters ko text ke jaisa count kar sakta hai, false hits deta hai.

S = p + # + t

use karo jahan

#

dono mein absent ho.

"while loop condition sirf s[Z[i]] == s[i+Z[i]] ho sakti hai."

Error missing bounds check hai. Tumhe yeh bhi require karna chahiye ki

i + Z [i] < n

, warna tum string ke end ke baad read karte ho aur ya toh crash hota hai ya garbage compare hota hai.

Z [i^{'}]

jahan

i^{'} = i - l

— main mirror ke liye

i - r

use karunga."

Error wrong endpoint ke against mirror karna hai. Box prefix ko mirror karta hai, jiska left end

l

se align hota hai, isliye prefix mein offset

i - l

hai,

i - r

nahi.

"Case A (

i > r

) ko Case B se alag special code chahiye."

Logic mein galti nahi hai lekin economy mein hai — Case A bas Case B hai jahan

Z [i]

0

se initialize hota hai aur koi cap nahi, isliye single while loop dono handle karta hai; alag branches likhna redundant hai.

Why questions

Hum box ko rightmost box kyun kehte hain, bas "a box" kyun nahi?

Kyunki un sab intervals mein jo prefix se match karte hain, hum woh rakhte hain jiska right end

r

sabse bada ho — yeh maximize karta hai ki kitne future positions

i

uske andar aate hain aur free mein answer paate hain.

Mirror value copy karna linear time kyun deta hai sirf ek achhi shortcut hone ki jagah?

Har position jo free mein answer paata hai usme zero comparisons lagti hain, isliye saara real character kaam while loop tak confined hai, aur woh loop

r

kitna aage badhta hai isse bounded hai — overall at most

n

steps.

Mirror ka match khatam karne wala mismatch sub-case B1 mein

i

par "dobara kyun hota hai"?

Kyunki woh mismatch ek aise position par hua tha jo box ke andar tha, aur box ke andar

s

prefix ki exact copy hai, isliye same mismatch corresponding spot par

i

ke paas bhi hona zaroori hai.

Naive method specifically

aaaa...a

par

O (n^{2})

kyun hai?

Har starting index prefix se end tak match karta hai, isliye index

i

lagbhag

n - i

comparisons karta hai, aur unhe sum karne par

\frac{n ^{2}}{2}

jaisa kaam milta hai.

Separator character dono

p

aur

t

mein absent kyun hona chahiye, sirf ek mein nahi?

Agar

#

kisi bhi string mein appear kare toh algorithm use ordinary character ki tarah match kar sakta hai, ek "match" ko boundary ke paas se leak hone de sakta hai aur aisi positions report karta hai jo poora pattern contain nahi karti.

min cap while ko pure B1 case mein zero kaam kyun karne deta hai?

Jab

Z [i - l] < r - i + 1

ho toh cap

Z [i] = Z [i - l]

chhod deta hai, aur test hone wala agla character ek aisi position par hota hai jahan mirror ne already mismatch find kiya tha, isliye pehli while comparison hi fail ho jaati hai aur koi extension nahi hoti.

Z [i]

ko prefix comparison mein

i

ke right ki positions use karke define kyun nahi kiya ja sakta?

Definition se

Z [i]

s [i ..]

s [0..]

se compare karta hai, yaani woh prefix jo hamesha position

0

se start hoti hai; comparison dono anchors se aage badhta hai, prefix start ke right ki kisi cheez ko kabhi reference nahi karta.

Edge cases

Length

1

ki string ke liye

Z [i]

kya hai, maano

s = a

Sirf

Z [0]

exist karta hai aur woh convention se

0

set hota hai; koi aur indices nahi hain, aur algorithm ka loop

1

n - 1

tak simply run hi nahi karta.

Ek string jahan har character distinct ho, jaise

abcd

, uske Z-array ka kya hoga?

i \geq 1

ke liye har

Z [i]

0

hoga, kyunki

0

ke baad koi position prefix ke pehle character

a

se start nahi karti; koi box kabhi nahi banta.

Agar pattern poore text ke barabar ho (

p = t

), toh pattern-matching build kya report karta hai?

S = p + # + t

mein separator ke baad wali position ka

Z = m

hoga, isliye yeh exactly ek match text index

0

par report karta hai — pattern poore text mein ek baar aata hai.

Z [n - 1]

(last position) at most kya hai, aur woh max kab hit karta hai?

At most

1

, kyunki sirf ek character bachta hai; yeh exactly

1

hota hai jab last character

s [0]

ke barabar ho, aur otherwise

0

Kya box

[l, r]

kabhi

l = r

ho sakta hai?

Haan. Jab koi position prefix se exactly ek character ke liye match kare (

Z [i] = 1

) aur pehle se aage tak pahunche, toh box ek single point

l = r = i

ban jaata hai, phir bhi ek valid "length 1 ke liye prefix se match" interval hai.

Agar

i = r

exactly ho (boundary par, strictly andar nahi)?

Yeh tab bhi Case B count hota hai (

i \leq r

): mirror ek value deta hai, cap

min (r - i + 1, \dots) = min (1, \dots)

at most

1

hai, aur while

r

ke baad koi bhi extension verify karta hai.

Kya

p + # + t

construction mein empty pattern ka koi matlab hai?

Empty pattern ka

m = 0

hota hai, isliye

Z [i] = 0 = m

"match" har jagah hoga, jo correctly reflect karta hai ki empty string har position par occur hoti hai — usually ise trivial special case ke taur par guard kiya jaata hai.

Related tools jo inhi tasks par Z-array se mukabla karte hain: KMP failure function, String Hashing, Suffix Array, Suffix Automaton, Manacher's Algorithm, aur Amortized Analysis argument jo linear bound ko underlie karta hai.