Suffix array — construction O(n log n), LCP array

3.8.7 · Coding › String Algorithms

Intuition The big picture (WHY this exists)

Ek suffix array basically sirf ek string ke saare suffixes ki list hai, sorted lexicographically, unke starting indices ke array ke roop mein stored.

WHY do we want this? Suffix tree same problems solve karta hai (substring search, longest repeated substring, etc.) lekin memory mein heavy aur code karna jhanjhati wala hai. Suffix array ~90% power ~20% pain mein deta hai — yeh ek flat integer array hai. Yahi 80/20 wala fayda hai.

WHAT it buys you: $s$ ka koi bhi substring kisi suffix ka prefix hota hai. Agar suffixes sorted hain, to pattern $p$ ke saare occurrences ek contiguous block banate hain jisme binary-search kar sako. LCP array (adjacent sorted suffixes ka longest common prefix) add karo aur tum distinct substrings count kar sakte ho, longest repeated substrings dhundh sakte ho, aur "kisi bhi do suffixes ka longest common prefix" $O (1)$ mein answer de sakte ho.

1. Definitions

Figure — Suffix array — construction O(n log n), LCP array

2. Construction in $O (n lo g n)$ — derived from scratch

HOW the cost comes out to $O (n lo g n)$ :

Rounds ki sankhya $= ⌈ lo g_{2} n ⌉$ (kyunki $k$ double hota hai: $1, 2, 4, \dots, \geq n$ ).
Har round mein $n$ pairs sort hote hain. Radix sort (chhote integer keys $\in [0, n]$ par do passes) se har round $O (n)$ ka hai. → total $O (n lo g n)$ .
Agar comparison sort use karo har round mein ( $O (n lo g n)$ ), total $O (n lo g^{2} n)$ hoga — phir bhi theek hai aur code karna bahut simple.

Worked example Build

$S A$ for $s = "banana"$ ( $n = 6$ ) Suffixes & indices:

0 banana   3 ana
1 anana    4 na
2 nana     5 a

Round k=1 (sort by 1 char): letter se rank. $a < b < n$ . indices sorted: pehle a's phir b phir n's → ranks $r_{1} = [1 (b), 0 (a), 2 (n), 0 (a), 2 (n), 0 (a)]$ wait — ties sirf letter se resolve hote hain. Assign: a→0, b→1, n→2. To $r_{1} = [1, 0, 2, 0, 2, 0]$ . Why this step? Hame sirf pehla letter pata hai; saare a's tie karte hain (rank 0).

Round k=2, key $= (r_{1} [i], r_{1} [i + 2])$ :

i=0: (1, 2)   i=3: (0, 0)
i=1: (0, 2)   i=4: (2, -1)
i=2: (2, 0)   i=5: (0, -1)

Pairs ascending sort karo → indices ka order: 5(0,-1),3(0,0),1(0,2),0(1,2),2(2,0),4(2,-1). New ranks $r_{2} = [3, 2, 4, 1, 5, 0]$ . Why? Ab 2 chars se lagbhag sab distinct hain; sirf ek aur round chahiye.

Round k=4, key $= (r_{2} [i], r_{2} [i + 4])$ :

i=0:(3,5) i=1:(2,0) i=2:(4,-1) i=3:(1,-1) i=4:(5,-1) i=5:(0,-1)

Saare keys distinct hain → final. Sort karo → $S A = [5, 3, 1, 0, 4, 2]$ . Check: suf(5)=a, suf(3)=ana, suf(1)=anana, suf(0)=banana, suf(4)=na, suf(2)=nana. ✅ sorted!

3. The LCP array — Kasai's $O (n)$ algorithm, derived

Intuition Why LCP can be built in linear time (the magic observation)

Suffixes ko starting index $i = 0, 1, \dots$ ke order mein process karo (sorted order mein NAHIN). $h$ = suffix $i$ aur uske sorted order mein predecessor ke beech ka LCP.

Steel-manned claim: jab hum suffix $i$ se suffix $i + 1$ par jaate hain, LCP zyada se zyada 1 girt hai.

WHY? Maano suffix $i$ aur suffix $j$ (jo $S A$ mein $i$ ke theek pehle hai) ke beech $h \geq 1$ length ka prefix shared hai. Tab $s [i] = s [j]$ aur remaining parts $suf (i + 1)$ aur $suf (j + 1)$ hain, jo already $h - 1$ length ka prefix share karte hain, AUR $suf (j + 1)$ sorted order mein $suf (i + 1)$ se pehle aata hai. To jo bhi suffix $i + 1$ ka actual predecessor hai woh kam se kam $h - 1$ characters share karta hai. Isliye $h$ ek step mein 1 se zyada nahin girta lekin forward scan se dubara badh sakta hai — total growth $n$ se bound hai, total shrink $n$ se → $O (n)$ amortized.

Worked example LCP for "banana",

$S A = [5, 3, 1, 0, 4, 2]$ rank $= [3, 2, 5, 1, 4, 0]$ (inverse). $i$ se walk karo:

i=0 rank3 pred=SA[2]=1: suf0=banana, suf1=anana → LCP 0. h=0→ h=0
i=1 rank2 pred=SA[1]=3: anana vs ana → match "ana"=3. LCP[2]=3. h=3-1=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 pred. h=0

Result sorted rank ke according: $LCP = [0, 1, 3, 0, 0, 2]$ . Why the +1 reuse at i=1→i=2? "ana" match karne ke baad (h=3) hum 2 par aate hain aur agla suffix actually kam se kam utna overlap se start karta hai — re-scan bachta hai.

4. Common mistakes (Steel-man → fix)

Recall Feynman: 12-saal ke bachche ko samjhao

Socho tumne "banana" jaisa ek word liya aur uske saare tails kaate: "banana", "anana", "nana", "ana", "na", "a". Ab in tails ko dictionary order mein rakh do jaise dictionary mein words hote hain. Suffix array sirf us sorted list mein page numbers (starting positions) hai. Unhe fast sort karne ke liye hum lazy hain: pehle sirf pehla letter compare karte hain, phir pehle do letters, phir chaar, har baar double karte hue — kyunki ek tail ke pehle 4 letters jaanne ke liye hum do "pehle 2 letters" ke answers jod lete hain jo hum already compute kar chuke hain. LCP numbers batate hain ki do neighbouring tails ke kitne starting letters same hain — repeats dhundne mein kaam aata hai.

Connections

Suffix Tree — same problems, zyada memory; SA uska flattened cousin hai.
Radix Sort / Counting Sort — per-round linear sort jo $O (n lo g n)$ enable karta hai.
Binary Search on Suffix Array — $O (m lo g n)$ mein pattern matching.
Sparse Table / RMQ — LCP ke saath combine karo kisi bhi do suffixes ka $O (1)$ LCP ke liye.
Z-Algorithm / KMP — alternative substring tools (single pattern).
Burrows–Wheeler Transform — suffix array se directly banta hai.

Flashcards

Suffix array of a string kya hota hai?

Saare suffixes ke starting indices ka array, lexicographically sorted.

Rank array kya hai aur SA se kaise relate karta hai?

rank inverse permutation hai: rank[SA[r]] = r; yeh har suffix ki sorted position deta hai.

O (n lo g n)

suffix array construction ka core idea kya hai?

Prefix-doubling: rank pairs (rank_k[i], rank_k[i+k]) use karke pehle k chars se sort karo, har round mein k double karo.

Agle round ki comparison key ek pair of previous ranks kyun hoti hai?

Suffix i ke pehle 2k chars = (suf i ke pehle k) + (suf i+k ke pehle k), jinke orders already known ranks hain.

Kitne doubling rounds aur total complexity (radix sort ke saath)?

⌈log₂ n⌉ rounds × O(n) each = O(n log n).

rank_k[i+k] ke liye sentinel kya ho jab i+k ≥ n, aur kyun?

−1 (kisi bhi real rank se chhota), kyunki chhota suffix uss longer suffix se pehle sort hona chahiye jo uska prefix share karta hai.

LCP[r] kya measure karta hai?

Do adjacent sorted suffixes suf(SA[r−1]) aur suf(SA[r]) ke longest common prefix ka length.

Kasai ke O(n) LCP algorithm ke peeche key lemma kya hai?

Suffix i se i+1 par jaate waqt, uske predecessor ke saath LCP zyada se zyada 1 se girta hai.

Kasai h ko reset karne ki jagah carry over kyun karta hai?

Amortized O(n) rakhne ke liye; reset karne se O(n²) re-scanning hoti hai.

SA aur LCP se distinct substrings ki sankhya ka formula?

Σ(n − SA[r]) − Σ LCP[r].

LCP kaun se suffixes compare karta hai, yeh common mistake kya hai?

Yeh sorted (SA) order mein neighbors compare karta hai, index r aur r+1 wale suffixes NAHIN.

1. Definitions

2. Construction in O(nlogn) — derived from scratch

3. The LCP array — Kasai's O(n) algorithm, derived

4. Common mistakes (Steel-man → fix)

Connections

Flashcards

Concept Map

2. Construction in $O (n lo g n)$ — derived from scratch

3. The LCP array — Kasai's $O (n)$ algorithm, derived