KYA HAI. Ek string lo. Ek suffix uss string ki ek tail hi hoti hai: koi starting position chuno aur bilkul end tak padho.
KYO HAI. Har substring jo aap kabhi bhi search kar sakte ho, kisi na kisi tail ka front part hoti hai. Toh agar hum tails ko samajh lein, hum sabhi substrings ko samajh lete hain. Yahi poori wajah hai ki yeh data structure exist karta hai.
PICTURE. Neeche, word banana ek baar likha gaya hai, aur har colored bracket mark karta hai ki ek tail kahan se shuru hoti hai aur end tak jaati hai. Har bracket ke neeche ka number uska starting indexi hai (hum 0 se count karte hain).
Exactly n suffixes hote hain — ek har starting position ke liye.
KYA HAI. Hum in tails ko sort karne wale hain waise jaise dictionary words sort karti hai: pehla letter compare karo; agar tie ho, doosra compare karo; aur aise hi aage. Yeh rule lexicographic order kehlata hai.
KYO HAI. Dictionary mein, sab words jo same letters se shuru hote hain ek block mein saath baithte hain. Yahan bhi same hai: sort karne ke baad, har tail jo same letters se shuru hoti hai ek contiguous run banati hai. Yahi contiguity baad mein binary search ko koi bhi pattern dhundhne deti hai.
PICTURE. Do tails ko column by column compare kiya jaata hai. Pehla column jahan woh differ karte hain winner decide karta hai — aur ek choti tail jo letters khatam ho jaane ke baad smaller treat ki jaati hai (string "ended", aur end-of-string sabse choti cheez hoti hai).
KYA HAI. Tails ko poore strings compare karke sort karna kaam karta hai, lekin har comparison n tak letters scan kar sakta hai, aur n tails hain — yeh bahut slow hai. Iske bajaaye hum sirf pehle k letters use karke sort karte hain har tail ke, aur k grow karte jayenge.
KYO HAI. Agar hum sirf pehle k letters dekhein, tails jo un k letters par agree karti hain tie karti hain. Hum ties ko ek rank se record karte hain: equal keys ko same rank number milta hai. Baad mein, k grow karna ties todata hai. Yeh "thoda dekho, phir thoda aur" hi fast method ka seed hai.
PICTURE.k=1 ke liye hum sirf pehla letter dekhte hain. a se shuru hone wali teeno tails tie karti hain (rank 0); b ko rank 1 milta hai; dono n wali tails tie karti hain (rank 2).
KYA HAI. Humare paas pehle k letters ke ranks hain (unhe rk kaho). Pehle 2k letters se sort karne ke liye, hum 2k letters dobara nahin padhte. Hum har tail ke liye ek pair key banate hain:
key2k(i)=(rk[i],rk[i+k])
KYO HAI.suf(i) ke pehle 2k letters do blocks mein split hote hain length k ke: i par shuru hone wala block, aur i+k par shuru hone wala block. Lekin "i+k par shuru hone wale pehle k letters" exactly suf(i+k) ka front hai, jise rk[i+k] pehle se hi rank karta hai! Toh pehla half rk[i] se summarize hota hai aur doosra half rk[i+k] se. Pair compare karna pehle 2k letters compare karna hai — un numbers se jo humare paas pehle se hain. Isliye yeh method prefix doubling kehlata hai.
PICTURE. Arrow dikhata hai ki ek tail ka doosra half itself ek choti tail ka front hai jise hum pehle se rank kar chuke hain. Yahi reuse poora magic hai.
KYA HAI. Jab i+k≥n ho, doosra block "string ke end ke baad se shuru hota hai" — wahan koi letters nahin hain. Us half ko special value −1 assign karte hain.
KYO HAI. Ek tail jo khatam ho gayi ho use kisi bhi tail ke pehle sort hona chahiye jo abhi bhi letters rakhti hai (Step 2 yaad karo: end-of-string sabse choti hoti hai). Agar hum lazily 0 ya garbage daal dein, toh ek choti tail jaise a galti se ek lambi tail jaise ana ke baad sort ho sakti hai jabki a pehle aani chahiye. −1 use karke, jo har real rank (0,1,2,…) se choti value hai, ended tail ko front par force karte hain.
PICTURE. Do tails jo apne pehle k letters par agree karti hain: ek ke paas aur letters hain, doosri khatam ho gayi hai. −1 tag ended wali ko pehle push karta hai.
Ab banana par pehla doubling round chalao: k=1, toh offset i+1 hai aur hum key2(i)=(r1[i],r1[i+1]) banate hain. r1=[1,0,2,0,2,0] ke saath:
i=0:(1,0) & i=1:(0,2) & i=2:(2,0) &\\
i=3:(0,2) & i=4:(2,0) & i=5:(0,-1) &
\end{array}$$
Term by term: $\text{key}_2(0)=(r_1[0],r_1[1])=(1,0)$ `ba` se; $\text{key}_2(5)=(r_1[5],-1)=(0,-1)$ kyunki `a` end se bahar chali jaati hai.
**Pairs ko ascending sort karne par** index order milta hai $5,3,1,0,4,2$:
$$5\!:\!(0,\text{-}1)\;<\;3\!:\!(0,2)=1\!:\!(0,2)\;<\;0\!:\!(1,0)\;<\;4\!:\!(2,0)=2\!:\!(2,0)$$
**Is sorted list se naye ranks $r_2$ kaise padhein** — sorted pairs ko left se right scan karo, counter $0$ se shuru karo; **equal keys ko same rank do, aur counter sirf tab $1$ bump karo jab key change ho**:
| position | index | key | key changed? | rank $r_2$ |
|---|---|---|---|---|
| 0 | 5 | $(0,-1)$ | start | $0$ |
| 1 | 3 | $(0,2)$ | yes | $1$ |
| 2 | 1 | $(0,2)$ | no (3 ke saath tie) | $1$ |
| 3 | 0 | $(1,0)$ | yes | $2$ |
| 4 | 4 | $(2,0)$ | yes | $3$ |
| 5 | 2 | $(2,0)$ | no (4 ke saath tie) | $3$ |
$r_2$ ko **starting index ke hisaab se** wapas likhne par (sorted position ke hisaab se nahin): $r_2=[2,1,3,1,3,0]$. Notice karo ki indices $1$ aur $3$ abhi bhi tie kar rahe hain (dono `an…`), aur $2$ aur $4$ abhi bhi tie kar rahe hain (dono `na…`) — do characters abhi bhi kaafi nahin hain. Ek aur round ($k=2$, offset $i+2$) yeh ties todega aur sort finish karega.
---
## Step 6 — $\log n$ rounds ke baad hum done hain: finished suffix array
**KYA HAI.** Har round $k$ ko **double** karta hai: $1 \to 2 \to 4 \to \dots$. Jab $k \ge n$ ho jaata hai, do alag tails abhi bhi tied nahin ho sakti, toh ranks true final order hain. Rounds ki sankhya $\lceil \log_2 n \rceil$ hai.
**COST $O(n\log n)$ KYO HAI.** $\lceil\log_2 n\rceil$ rounds hain. Har round mein $n$ pairs sort karni padti hain jinke entries $[-1, n)$ mein integers hain. Naive comparison sort har round mein $O(n\log n)$ cost karta hai → total $O(n\log^2 n)$ (code karna simple, contests mein theek hai). True $O(n\log n)$ paane ke liye har round ko $O(n)$ mein sort karte hain ek **two-pass [[Radix Sort|radix sort]]** use karke jo [[Counting Sort|counting sort]] se bana hota hai:
> [!intuition] Do passes kyo aur *stable* sorting essential kyo hai
> Ek pair key ke do coordinates hain $(a,b)=(r_k[i],\,r_k[i+k])$. Radix sort **least-significant coordinate pehle** sort karta hai: pass 1 sabhi indices ko $b$ (second half) se sort karta hai, pass 2 $a$ (first half) se sort karta hai. Final order sahi hone ke liye, pass 2 ko **disturb nahin karna chahiye** woh order jo pass 1 ne equal $a$'s ke beech establish kiya — yeh property ==stability== kehlati hai. [[Counting Sort]] stable hota hai agar aap equal keys ko first-seen order mein place karo, toh $a$ par ties apni pass-1 ordering by $b$ rakhti hain. Har pass $n$ items ko $[0,n)$ mein keys ke saath touch karta hai, toh har pass $O(n)$ hai aur round $O(n)$ hai.
$O(n)$ per round ko $\lceil\log_2 n\rceil$ rounds se multiply karo → $O(n\log n)$.
**PICTURE.** Tails ki final sorted list, array $SA$ = unke starting indices upar se neeche padhe gaye.
![[deepdives/dd-coding-3.8.07-d2-s06.png]]
> [!definition] Suffix array $SA$ aur rank array
> $$SA = [\,5,\ 3,\ 1,\ 0,\ 4,\ 2\,]$$
> - $SA[r]$ ::: $r$-th sabse choti tail ka starting index
> - $\text{rank}[i]$ ::: tail $i$ sorted order mein kahan aayi — $SA$ ka *inverse*
> Yahan $\text{rank} = [3,2,5,1,4,0]$, matlab $\text{rank}[SA[r]] = r$ har $r$ ke liye.
---
## Step 7 — Neighbors measure karna: LCP array
**KYA HAI.** Ab jab tails sort ho gayi hain, pucho: kitne starting letters har tail sorted list mein **bilkul upar wali tail** se share karti hai? Woh count *adjacent-in-sorted-order* tails ka **LCP** (Longest Common Prefix) hai.
**KYO HAI.** Sorted list mein neighbors *sabse zyada similar* tails hain possible. Unki shared prefix length string mein repeats reveal karti hai aur, sum karke, distinct substrings count karti hai. Sirf neighbors compare karna (sab pairs nahin) kaafi hai kyunki koi bhi do tails ki shared prefix unke beech ke run ke LCPs se bounded hoti hai.
**PICTURE.** Sorted list phir se, ab har pair of neighbors ke beech ek bracket hai jo dikhata hai kitne leading letters match karte hain.
![[deepdives/dd-coding-3.8.07-d2-s07.png]]
> [!definition] LCP array
> $\text{LCP}[r]$ = $\text{suf}(SA[r-1])$ aur $\text{suf}(SA[r])$ ke beech shared leading letters ki sankhya, $r = 1,\dots,n-1$ ke liye; aur $\text{LCP}[0]=0$.
> `banana` ke liye: $\text{LCP} = [\,0,\ 1,\ 3,\ 0,\ 0,\ 2\,]$.
> - $\text{LCP}[2]=3$ ::: `ana` aur `anana` `ana` share karte hain
> - $\text{LCP}[5]=2$ ::: `na` aur `nana` `na` share karte hain
> [!mistake] "LCP[r] suffix index $r$ ko index $r+1$ se compare karta hai."
> *Sahi lagta hai:* woh adjacent lagte hain. *Sachai:* adjacency **sorted order** mein hai, yaani $SA[r-1]$ vs $SA[r]$ — raw indices nahin. **Fix:** hamesha kaho "array mein neighbors."
---
## Step 8 — Kasai's linear-time LCP: "at most 1 drop" wala lemma
**KYA HAI.** Har LCP scratch se recompute karne ki jagah, tails ko **starting index** $i=0,1,2,\dots,n-1$ ke order mein walk karo aur ek **single running match length** $h$ carry karo jo hum *ek baar* $0$ se initialize karte hain aur kabhi haath se reset nahin karte.
**KYO (lemma).** Maano $\text{suf}(i)$ apne sorted predecessor ke saath $h$ letters share karta hai. Dono ka pehla (shared) letter kaato: hume $\text{suf}(i+1)$ milta hai aur ek tail jo abhi bhi $h-1$ letters share karti hai usse *aur* abhi bhi sorted order mein pehle baithti hai. Toh $\text{suf}(i+1)$ ka true predecessor **kam se kam** $h-1$ letters share karta hai. Isliye $h$ zyada se zyada $1$ per step gir sakta hai. Yeh sirf forward scanning se badhta hai, aur sabhi steps mein total forward scanning $n$ se bounded hai → **$O(n)$ overall**.
**PICTURE.** Left: tail $i$ ke liye $h$ letters match kiye. Right: ek letter hatao, aur guaranteed $h-1$ overlap tail $i+1$ ke liye survive karta hai — un letters ko dobara scan karne ki zarurat nahin.
![[deepdives/dd-coding-3.8.07-d2-s08.png]]
> [!formula] Kasai's algorithm — exact loop
> ```
> h = 0 # EK variable, ek baar initialize
> for i in 0, 1, 2, ..., n-1: # starting index se walk karo
> if rank[i] == 0: # suf(i) sabse chota hai -> koi predecessor nahin
> h = 0 # uske upar kuch compare karne ko nahin; h = 0 rakho
> continue
> j = SA[rank[i] - 1] # predecessor ka starting index
> while i+h < n and j+h < n and s[i+h] == s[j+h]:
> h = h + 1 # match ek letter ek baar extend karo
> LCP[rank[i]] = h # record karo
> h = max(h - 1, 0) # guaranteed overlap aage carry karo
> ```
> - $h$ ::: loop se pehle **ek baar** $0$ par initialize; poora method *ise reset na karne* par depend karta hai
> - `rank[i] == 0` case ::: genuinely koi neighbor upar nahin hai, toh LCP undefined/`0` hai; yahan $h=0$ set karna woh forbidden reset **nahin** hai — bas carry karne ko kuch nahin hai, kyunki sabse chote suffix ka koi predecessor nahin hota
> - `while` guards ::: `i+h<n` aur `j+h<n` humein kisi bhi tail ke end ke baad padhne se rokta hai
> - $h=\max(h-1,0)$ ::: *sirf* ek decrement, record karne ke baad — yahi total work ko $O(n)$ rakhta hai
> [!mistake] **Har** iteration par $h=0$ reset karna.
> *Sahi lagta hai:* nai tail, naya count. *Cost:* aap guaranteed overlap phek dete ho aur sab kuch dobara scan karte ho → $O(n^2)$. **Fix:** $h$ ko loop ke *bahar* declare karo, ek baar $0$ se initialize karo, aur sirf `h += 1` (extend) ya `h = max(h-1, 0)` (carry) se change karo. Single exception "no predecessor" branch hai (`rank[i]==0`), jahan upar compare karne ko kuch nahin — yeh genuine absence of overlap hai, mushkil se kamayi progress ka reset nahin.
> [!example] Kasai on "banana", $SA=[5,3,1,0,4,2]$, $\text{rank}=[3,2,5,1,4,0]$
> ```
> h=0 start
> i=0 rank3 pred=SA[2]=1: banana vs anana -> 0 match. LCP[3]=0. h=max(-1,0)=0
> i=1 rank2 pred=SA[1]=3: anana vs ana -> "ana"=3. LCP[2]=3. h=2
> i=2 rank5 pred=SA[4]=4: nana vs na -> "na"=2. LCP[5]=2. h=1
> i=3 rank1 pred=SA[0]=5: ana vs a -> "a"=1. LCP[1]=1. h=0
> i=4 rank4 pred=SA[3]=0: na vs banana-> 0. LCP[4]=0. h=0
> i=5 rank0: no predecessor -> h=0, continue
> ```
> Result indexed by sorted rank: $\text{LCP}=[0,1,3,0,0,2]$. $i=2$ mein $h=2$ carry kiya gaya ($0$ se dobara scan karne ki jagah) — exactly woh amortization hai jo lemma ne promise kiya tha.
---
## Step 9 — Payoff: LCP array se distinct substrings count karna
**KYA HAI.** $s$ ki har substring exactly ek tail ka front hai. Agar hum har sorted tail ke, uske sabhi prefixes list karein, toh hum har substring count karte hain — lekin duplicates ke saath. LCP exactly batata hai ki kitne prefixes ek tail apne predecessor ke saath share karti hai, toh hum unhe subtract karte hain.
**KYO HAI.** Tail $SA[r]$ ke $n - SA[r]$ prefixes hain. Unme se, pehle $\text{LCP}[r]$ pehli tail mein already aaye (yahi "shared prefix" ka matlab hai). Overlaps subtract karo taaki har distinct substring ek baar count ho.
**PICTURE.** Ek staircase: har tail ke prefixes stack kiye gaye, LCP-shared portion "already counted" ke roop mein shaded hai.
> [!formula] Distinct-substring count
> $$\#\text{distinct} = \sum_{r=0}^{n-1}\big(n - SA[r]\big)\; -\; \sum_{r=1}^{n-1}\text{LCP}[r]$$
> - $n - SA[r]$ ::: prefixes (substrings) ki sankhya jo tail $SA[r]$ contribute karti hai
> - $\sum \text{LCP}[r]$ ::: total prefixes jo kisi predecessor ne pehle se count kiye
>
> `banana` ke liye: $\sum(n-SA[r]) = 1+3+5+6+2+4 = 21$ aur $\sum\text{LCP} = 0+1+3+0+0+2 = 6$, toh $\#\text{distinct} = 21 - 6 = 15$.
---
## Ek-picture summary
Poori pipeline ek page par: tails mein kato → doubling se pair keys aur $-1$ sentinel ke saath sort karo → $SA$ padho → Kasai se neighbor overlaps measure karo LCP paane ke liye → results nikalo.
> [!recall]- Feynman retelling — poora walk plain words mein
> `banana` ko uski sabhi tails mein kaato aur imagine karo unhe dictionary order mein rakhna. Fast sort karne ke liye hum lazy hain: pehle sirf ek letter compare karo (bahut saari ties), phir do, phir chaar, har baar double karte hue. Doubling ko cheap banane wala trick yeh hai ki ek tail ke *agli $k$ letters* ek choti tail ke *pehle $k$ letters* hain jise hum pehle se rank kar chuke hain — toh hum letters dobara padhne ki jagah **rank numbers ke pairs** compare karte hain, aur jitna hum aage dekhte hain uska offset exactly current $k$ hota hai (1, phir 2, phir 4…). Jab tails string ke end par pahunch jaati hain toh unhein $-1$ tag milta hai taaki woh front par float karein, bilkul waise jaise dictionary mein sabse chota word jeet jaata hai. Ek round ke sorted pairs ko wapas ranks mein badhalne ke liye unhe ek baar scan karte hain, equal pairs ko same number dete hain aur sirf tab bump karte hain jab pair change ho. Kyunki keys chhote integers hain hum har round ko ek *stable* two-pass counting/radix sort se linear time mein sort kar sakte hain, toh poora build $n\log n$ hai. Phir hum measure karte hain ki har tail kitne starting letters uske upar wali ke saath share karti hai — yeh LCP array hai — aur Kasai's trick kehti hai ki yeh count har baar sirf ek se gir sakta hai jab hum next start position par shift karte hain (ek carried variable $h$ use karke), toh sabhi measure karna linear work hai. Un overlap numbers se hum instantly count kar sakte hain ki `banana` ke 15 distinct substrings hain.
> [!recall]- Self-test
> Round $2k$ mein aap kis key se sort karte ho? ::: Pair $(r_k[i],\ r_k[i+k])$ — do length-$k$ halves ke ranks; offset $k$ $1$ se shuru hota hai aur har round mein double hota hai.
> Sorted pairs ko naye rank array mein kaise badlate ho? ::: Left se right scan karo, counter $0$ se shuru karo, equal keys ko same rank do, aur sirf tab increment karo jab key change ho; rank ko starting index se wapas likho.
> Per-round sort stable kyun hona chahiye? ::: Radix 2nd coordinate se phir 1st se sort karta hai; stability 1st par ties ke beech 2nd-coordinate order rakhti hai, toh pair order sahi rehta hai — aur har pass $O(n)$ rehta hai.
> $i+k\ge n$ par $-1$ kyun? ::: Tail khatam ho gayi; end-of-string sabse choti hoti hai, toh pehle sort honi chahiye.
> Kasai $O(n)$ kyun hai? ::: Ek carried variable $h$ zyada se zyada $1$ per step girta hai, toh total scanning $n$ se bounded hai.
> `banana` ke distinct substrings? ::: $21 - 6 = 15$.
Related maps: [[Suffix Tree]], [[Sparse Table / RMQ]] ($O(1)$ LCP queries ke liye), [[Z-Algorithm]], [[KMP]], [[Burrows–Wheeler Transform]].
