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

Position $4$ se run shuru hoti hai $s[4]s[5]s[6]=\text{aba}$. Prefix shuru hoti hai $s[0]s[1]s[2]=\text{aba}$ se.

• Compare $s[0]=\text{a}$ vs $s[4]=\text{a}$ ✓ (length abhi tak 1)
• Compare $s[1]=\text{b}$ vs $s[5]=\text{b}$ ✓ (length 2)
• Compare $s[2]=\text{a}$ vs $s[6]=\text{a}$ ✓ (length 3)
• Next hota $s[7]$, jo exist hi nahi karta → stop.

Toh $==Z[4]=3==$. Match ruka kyunki hum string ke end se bahar chale gaye, kisi mismatch ki wajah se nahi.

aaaaa ki har suffix khud a's ka run hai jo prefix ke barabar hai, lekin sirf utne characters tak jitne bache hain.

$Z[1]$: index 1 se 4 characters bache hain, sab a, sab prefix se match karte hain → $4$. Har baad waale index mein ek character kam bachta hai. Answer: $Z=[-,4,3,2,1]$.

Start $l=r=0$, $Z[0]=0$.

• $i=1$: $i>r=0$ → Case A. Compare $s[0]=\text{a}$ vs $s[1]=\text{b}$ ✗ → $Z[1]=0$. Koi box nahi.
• $i=2$: $i>r=0$ → Case A. ababab vs prefix ababab sab 6 remaining match karte hain → $Z[2]=6$. Box $l=2,r=7$.
• $i=3$: $i=3\le r=7$ → Case B. Mirror $i^{\prime }=1$, $Z[1]=0$, cap $r-i+1=5$, $\min (5,0)=0$; while: $s[0]=\text{a}$ vs $s[3]=\text{b}$ ✗ → $Z[3]=0$.
• $i=4$: $\le r$ → Case B. $i^{\prime }=2$, $Z[2]=6$, cap $r-i+1=4$, $\min (4,6)=4$; while: $s[4]=\text{a}$? hum $s[Z]=s[4]=\text{a}$ vs $s[i+Z]=s[8]$ test karte hain — range se bahar → stop. $Z[4]=4$. Naya box? $i+Z-1=7$, $>r=7$ nahi, toh update nahi.
• $i=5$: $\le r$ → Case B. $i^{\prime }=3$, $Z[3]=0$, cap $=3$, $\min =0$; while $s[0]=\text{a}$ vs $s[5]=\text{b}$ ✗ → $Z[5]=0$.
• $i=6$: $\le r$ → Case B. $i^{\prime }=4$, $Z[4]=4$, cap $r-i+1=2$, $\min (2,4)=2$; while $s[2]=\text{a}$ vs $s[8]$ range se bahar → stop. $Z[6]=2$.
• $i=7$: $\le r$ → Case B. $i^{\prime }=5$, $Z[5]=0$, cap $=1$, $\min =0$; while $s[0]=\text{a}$ vs $s[7]=\text{b}$ ✗ → $Z[7]=0$.

$Z=[-,0,6,0,4,0,2,0]$.

$S=\text{aab\#aababaab}$, length $m+1+n=3+1+8=12$. Indices:

Hume $Z[i]=3$ chahiye. Text region check karte hain ($i\ge 4$):

• $i=4$: aab vs prefix aab ✓✓✓, phir $S[3]=\text{\#}$ vs $S[7]=\text{a}$ ✗ → $Z[4]=3$. Hit.
• $i=9$: aab vs aab ✓✓✓, phir end se bahar → $Z[9]=3$. Hit.
• Baaki sab positions $Z<3$ dete hain.

Position convert karo $=i-(m+1)=i-4$:

• $i=4\Rightarrow t$-position $0$.
• $i=9\Rightarrow t$-position $5$.

Toh $p=\text{aab}$, $t$-positions $==\{0,5\}==$ par occur karta hai. Check: $t[\mathrm{0..2}]=\text{aab}$ ✓, $t[\mathrm{5..7}]=\text{aab}$ ✓.

$i=4$ par: cap $=\min (r-i+1,Z[i-l])=\min (4,6)=4$, toh loop entered hua $Z[4]=4$ ke saath. Phir isne s[4] == s[8] test kiya — lekin $i+Z=4+4=8=n$ range se bahar hai, toh while condition i+Z[i] < n turant false hai. Zero character comparisons. Value 4 mirror knowledge se copy ki gayi, bilkul free mein verify hui.

$i=2$ par (Case A): humne $Z[2]=0$ se start kiya aur scratch se compare karna pada: 6 successful matches phir end se bahar → 6 character comparisons. Yahi "real work" hai jisne $r$ ko $0$ se $7$ tak push kiya.

Key insight: $i=4$ par free copy exactly wahi reuse hai jo box humein dilata hai — mirror par $i^{\prime }=2$ ne already un matches ke liye pay kar diya tha.

Jab hum inhe process karte hain, box $l=3,r=5$ hai.

• $i=4$: mirror $i^{\prime }=1$, $Z[1]=1$. Box edge distance $r-i+1=5-4+1=2$. Kya $Z[i^{\prime }]<r-i+1$? $1<2$ ✓ → B1. Mirror ka match (length 1) aur uska terminating mismatch dono strictly box ke andar hain, toh $Z[4]=1$ bina kisi comparison ke copy ho jaata hai.
• $i=5$: mirror $i^{\prime }=2$, $Z[2]=0$. Edge distance $r-i+1=1$. Kya $0<1$? Haan → yeh bhi B1 hai ($Z[i^{\prime }]$ fit ho jaata hai). Hum $Z[5]=0$ copy karte hain; while ek baar $s[0]$ vs $s[5]$ test karta hai aur fail hota hai, kuch add nahi hota.

Yahaan koi true B2 nahi hai, kyunki koi mirror value box boundary tak pahunchi hi nahi. B2 ka example: abababab mein $i=4$ par, $Z[i^{\prime }]=6\ge$ edge $4$, toh isne cap hit kiya — yahi B2 shape hai (humne min pe rely kiya taaki unchecked territory claim na ho jaaye).

Length $k$ ka prefix position $i$ se start hota hua occur karta hai iff $Z[i]\ge k$ (wahaan se kam se kam $k$ lamba match shuru hota hai). Hum position $0$ ko bhi hamesha count karte hain.

ababa ke liye $Z$ build karo:

• $i=1$: $s[0]=\text{a}$ vs $s[1]=\text{b}$ ✗ → $Z[1]=0$.
• $i=2$: aba vs aba → 3 matches, end se bahar → $Z[2]=3$. Box $l=2,r=4$.
• $i=3$: $\le r$, mirror $i^{\prime }=1$, $Z[1]=0$, cap $=2$, $\min =0$; $s[0]=\text{a}$ vs $s[3]=\text{b}$ ✗ → $Z[3]=0$.
• $i=4$: $\le r$, mirror $i^{\prime }=2$, $Z[2]=3$, cap $r-i+1=1$, $\min (1,3)=1$; while $s[1]=\text{b}$ vs $s[5]$ range se bahar → $Z[4]=1$.

$Z=[-,0,3,0,1]$. Positions count karo (including 0) jahan $Z[i]\ge 2$: position $0$ (prefix khud), $i=2$ ($Z=3\ge 2$). Total $==2==$ occurrences of ab. Aankhon se check karo: ababa → ab indices $0$ aur $2$ par. ✔

Hume wo positions chahiye jahan match exactly end tak jaata ho: $i+Z[i]=n=10$.

Relevant Z-values haath se compute karo:

• $i=5$: run abcab vs prefix abcab → 5 match karta hai (s[5..9]=abcab, prefix abcab), phir end se bahar → $Z[5]=5$, aur $5+5=10$ ✓. Border length $5$.
• Koi longer? Length $6$ ke border ko $Z[4]=6$ with $4+6=10$ chahiye hoga; lekin $s[4]=\text{b}\ne s[0]=\text{a}$ → $Z[4]=0$. Nahi.

Longest proper border length $===5==$ (abcab). Check: prefix abcab = suffix abcab of abcababcab. ✔ Yahi exactly woh information hai jo KMP failure function store karta hai; Z iske liye ek alternative route deta hai.

$r$ sirf box-update line ke andar change hota hai, jo fire karta hai iff $i+Z[i]-1>r$, aur set karta hai $r\leftarrow i+Z[i]-1$. Apne hi guard se, naya $r$ strictly puraane $r$ se bada hai. Koi doosri line $r$ ko touch nahi karti. Isliye $r$ (weakly) non-decreasing hai — actually strictly increasing jab bhi change hota hai. ∎

while work ka bound. Har successful while iteration position $i+Z[i]$ par ek character match karti hai jo puraane $r$ se bahar tha (positions $\le r$ already known the, toh extension sirf $r$ ke baad hoti hai), aur phir $r$ use cover karne ke liye advance hota hai. Kyunki $r$ $0$ se start hota hai, har success par strictly increase karta hai, aur hamesha $\le n-1$ rehta hai, toh poore run mein at most $n$ successful while iterations hoti hain. Har $i$ mein at most ek failing while test bhi hota hai (woh mismatch jo uska loop end karta hai), total $\le n$ additional constant-cost tests deta hai. Total: $O(n)$. Pattern matching ke liye $O(m)$ concatenation ke saath combine karo → $==O(n+m)==$.

• (a) empty string $n=0$: array empty hai, $Z=[]$. Process karne ke liye koi positions nahi; loop for i in 1..n-1 zero baar chalta hai. Valid.
• (b) x, $n=1$: $Z=[-]$ (sirf $Z[0]$, unused). Loop $i=1>n-1=0$ se start hota hai, toh kabhi nahi chalta. Match karne ke liye koi proper suffix nahi hai.
• (c) yy, $n=2$: $i=1$, Case A, $s[0]=\text{y}$ vs $s[1]=\text{y}$ ✓, phir end se bahar → $Z[1]=1$. Toh $Z=[-,1]$.
• (d) a^k (letter $k$ baar repeat): L1.2 pattern se, $Z[i]=k-i$ for $i\ge 1$. Formula: $==Z[i]=k-i==$. Yeh naive algorithm ke liye worst case hai (${\sum }_i(k-i)=\Theta (k^2)$) lekin box-based algorithm fir bhi $O(k)$ mein run karta hai: box $i=1$ par poori tail cover karne ke liye jump karta hai, aur har baad wala $i$ ek free B1 copy hota hai.

• Strong feel ho raha hai? Z ko KMP failure function se compare karo — dono different mechanics se closely related border information compute karte hain.
• Prefix matching ki jagah hashing se matching ke liye, String Hashing dekho.
• Is reuse trick ka palindrome-flavored cousin: Manacher's Algorithm.
• Heavier full-text index structures: Suffix Array, Suffix Automaton.
• Linear-time proof style generalizes: Amortized Analysis.
• Core ka Hinglish walkthrough: 3.8.04 Z-algorithm — Z-array construction, O(n+m) (Hinglish).