3.8.4 · D1Z-algorithm — Z-array construction, O(n+m)
Z-algorithm ek kaam karta hai — kisi bhi word mein har starting spot ke liye ye poochta hai: "yahan se kitne letters word ke bilkul shuru se match karte hain?" — aur ye kaam karta hai ek left-to-right sweep mein, jo matches pehle mil chuke hain unhe reuse karke, baar baar count karne ki bajaye. Neeche jo bhi hai wo wahi vocabulary hai jo tumhe chahiye taaki ye sentence poori tarah samajh aaye.
Z-array banane se pehle tumhe kuch choti choti ideas mein fluent hona padega: ek string actually kya hoti hai numbered boxes ki row ke roop mein, ek prefix aur substring pictures mein kaisi dikhti hain, ek interval [ l , r ] photocopy ho. Chalte hain, ek ek ko samjhte hain.
Definition String aur uske indicesEk string s index kehte hain. Hum counting 0 0-indexed kehte hain), toh pehla box index 0 1 length kehte hain, jo n
0 1 i ′ = i − l 0 1
Intuition Woh picture jo dimaag mein rakhni haiFigure dekho: string labelled boxes ki ek strip hai. Index woh address hai jo har box ke neeche likha hai; character woh cheez hai jo box ke andar rehti hai. Jab hum baad mein "position i i
Notation jo ab har jagah dikhegi:
Definition Prefix, suffix, substring
Prefix ek aisi strip hai jo bilkul shuru se start hoti hai (index 0 s [ 0.. k − 1 ] k Suffix ek aisi strip hai jo bilkul end par khatam hoti hai (index n − 1 Substring koi bhi connected strip s [ a .. b ]
Z-algorithm sirf ek khaas comparison ki parwah karta hai: ye ek aisi substring leta hai jo kisi index i hoti hai aur poochta hai ke uska kitna hissa prefix se agree karta hai. Toh in teeno mein se, prefix star hai aur index i woh cheez hai jo hum uske saamne rakhte hain.
Worked example Shapes ko identify karos = aabxaab 7
Length 3 s [ 0..2 ] = aab
i = 4 s [ 4..6 ] = aab Ye dono strips equal hain! Length 3 Z [ 4 ]
Definition Do strips match karti hainSame length ki do strips match karti hain jab har box align ho: ek ki character 0 0 1 1
Ab poore topic ki core baat — ek strip ko prefix ke against compare karna aur pehli disagreement pe rokna.
Intuition "Longest matching length" kyun, sirf "kya ye match karte hain?" kyun nahi?Haan/Nahi wala "kya ye match karte hain?" information throw away kar deta hai. Z-algorithm ko exact number chahiye — kitne boxes agree karte hain pehli mismatch se pehle — kyunki wohi number ek baad wali position ko pehle ka jawab copy karne deta hai. Isliye hum hamesha agreement ki length maapte hain, sirf haan/nahi nahi.
Z s = aabxaab i = 4 aab aab 3 Z [ 4 ] = 3 i = 1 a s [ 0 ] s [ 2 ] = b = s [ 1 ] = a 1 Z [ 1 ] = 1
Ek interval [ l , r ] l r l left edge hai aur r right edge hai. Agar l > r empty hai (kisi cheez ko point nahi karta) — ye woh starting state hai jab humne kuch nahi dhoondha hota.
Algorithm ek ki jagay do numbers kyun carry karta hai? Kyunki use ek poori stretch yaad rakhni hoti hai jo already verify ho chuki hai — ek single spot nahi. Pair [ l , r ]
Intuition Z-box beginning ka ek photocopy haiJab algorithm ne prove kar diya ki strip s [ l .. r ] s [ 0.. r − l ] barabar hai, toh wo [ l , r ] Z-box kehta hai. Ise ek photocopy ki tarah socho — string ke front ka, box l i i − l
Agar i [ l , r ] mirror i ′ = i − l i i ′
Koi bhi aisa scenario nahi aana chahiye jo foundations ne nahi dikhaya, isliye ye chote edge inputs hain:
Worked example Degenerate inputs
Shuru mein empty box status l = r = 0 hum abhi kuch nahi jaante, toh pehli real position (i = 1 Z [ i ] = 0 i immediately s [ 0 ] Z [ 0 ] 0 n End se bahar jaana: agar comparison index n
Definition Amortized costAmortized cost ka matlab hai: ye mat poochho "ek step kitna expensive hai?", ye poochho "poora run kitna expensive hai steps ki sankhya se divide karne par ?". Ek single step kabhi kabhi bahut kaam kar sakta hai, lekin agar aise steps rare hain, toh average chota rehta hai.
Parent ka linear-time claim is idea par tika hai (Amortized Analysis mein gehraai se samjhaya gaya hai): har real character comparison right edge r , r r n n
Index and character s of i
Match and length of agreement
Z-box photocopy of prefix
Upar har ek foundation Z-algorithm — Z-array construction, O(n+m) parent note ko feed karta hai. Related string tools jo inhi ideas ko reuse karte hain: KMP failure function , String Hashing , Suffix Array , Suffix Automaton , Manacher's Algorithm . Hindi walkthrough prefer karte ho? Dekho 3.8.04 Z-algorithm — Z-array construction, O(n+m) (Hinglish) .
s = aabx s [ 2 ] Character b 2
s [ 1..3 ] Index 1 3 abx
Kisi string ka prefix kya hota hai? Koi bhi strip jo index 0
Ek sentence mein, Z [ i ] Index i
Interval [ l , r ] Address l r
[ l , r ] Strip s [ l .. r ] s [ 0.. r − l ]
Agar i [ l , r ] i ′ = i − l
Box ke andar s [ i ] = s [ i − l ] Kyunki box prefix ka photocopy hai, toh left edge se same distance matlab same character.
r − i + 1 Position i r
Z [ i ] = 0 i s [ 0 ]
Ek line mein, total cost O ( n ) Har real comparison r r n n
