Suffix array — construction O(n log n), LCP array: Worked examples

3.8.7 · D3 · Coding › String Algorithms › Suffix array — construction O(n log n), LCP array

Yeh parent Suffix-Array note ka hands-on companion hai. Parent ne machinery banai thi; yahan hum us machinery ko har tarah ke input par chalate hain jo ek problem tumhe de sakti hai — including woh weird degenerate cases jo naive code ko tod dete hain.

Scenario matrix

Har string jo tum kabhi bhi suffix array mein daaloge, woh in cells mein se kisi ek mein aati hai. Last column us example ka naam batata hai jo ise pin karta hai.

Cell	Scenario class	Kya break ho sakta hai	Example
A	Generic mixed string	prefix-doubling rounds, sentinel $- 1$	Ex 1 (`mississippi`)
B	Sab characters equal (`aaaa`)	har suffix ek prefix share karta hai; LCP ek staircase hai	Ex 2
C	Sab characters distinct (`abcd`)	pehla round already finish ho jaata hai; LCP sab zero	Ex 3
D	Length 1 (`a`)	ek suffix, koi adjacent pair nahi, koi LCP entry nahi	Ex 4
E	Empty string ( $n = 0$ )	loops nahi chalane chahiye; array empty hai	Ex 4
F	Kasai "drop by at most 1" reuse	$h$ galat reset karna → $O (n^{2})$	Ex 5
G	Word problem — pattern search	binary-search block contiguous hona chahiye	Ex 6
H	LCP se distinct substrings count karna	do sums mein off-by-one	Ex 7
I	Exam twist — do suffixes ka LCP via RMQ	non-adjacent pair ka LCP range-min chahta hai	Ex 8

Cells A–I sab neeche cover hain. Chalte hain inhe walk karte hue.

Ex 1 — Cell A: ek generic string, full doubling

Worked example

$s = "mississippi"$ ke liye $S A$ banao, $n = 11$ Forecast: Guess karo suffix "i" (index 10) kahan land karega. Sabse chhota? Kahin beech mein? Padhne se pehle apna guess likho.

Suffixes (0-indexed):

0  mississippi   6  sippi
1  ississippi    7  ippi
2  ssissippi     8  ppi
3  sissippi      9  pi
4  issippi      10  i
5  ssippi

Step 1 — round $k = 1$ , pehle letter se sort karo. Yeh step kyun? Abhi hum kuch nahi jaante, toh hum sirf ek character par trust karte hain. Present letters ka alphabet order: i < m < p < s. Ranks assign karo i→0, m→1, p→2, s→3. $r_{1} = [1, 0, 3, 3, 0, 3, 3, 0, 2, 2, 0]$ (har index ka letter padhte hain: m,i,s,s,i,s,s,i,p,p,i).

Step 2 — round $k = 2$ , key $= (r_{1} [i], r_{1} [i + 2])$ . Yeh step kyun? Do characters un suffixes ko distinguish karte hain jo ek par tie karte hain. $i + 2 \geq 11$ ke liye hum sentinel $- 1$ use karte hain (end-of-string kisi bhi letter se chhota hai — parent ke mistake box mein dekho).

Step 3 — doubling jaari rakho $k = 4, 8$ . Kyunki $⌈ lo g_{2} 11 ⌉ = 4$ , chaar rounds ke baad ( $k = 1, 2, 4, 8$ ) $k \geq n$ aur ranks final hain.

Result: $S A = [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2]$ Toh suffix "i" (index 10) sabse chhota hai — yeh pehle sort hota hai. Kya tumhara forecast match kiya?

Verify: pehle chaar sorted suffixes hain i < ippi < issippi < ississippi — har ek ya toh prefix hai ya lexicographically next se chhota hai. ✅ Sahi sorted hai (VERIFY mein check kiya).

Ex 2 — Cell B: sab characters equal

Worked example

$s = "aaaa"$ , $n = 4$ Forecast: Jab har letter identical hai, toh kaun sa suffix sabse chhota hai — sabse lamba ya sabse chhota? Abhi guess karo.

Step 1 — equal-prefix suffixes ke liye ordering rule. Yeh step kyun? Jab do suffixes har shared character par agree karte hain, toh chhota wala jeeeta hai (woh pehle "khatam" hota hai, aur end-of-string sabse chhoti cheez hai). Toh "a" < "aa" < "aaa" < "aaaa". $S A = [3, 2, 1, 0]$ Sabse chhota suffix (index 3, sirf "a") pehle sort hota hai.

Step 2 — LCP ek perfect staircase hai. Yeh step kyun? Adjacent sorted suffixes hain "a" & "aa" (share "a", LCP $= 1$ ), phir "aa" & "aaa" (share "aa", LCP $= 2$ ), phir "aaa" & "aaaa" (LCP $= 3$ ). $LCP = [0, 1, 2, 3]$

Verify: $\sum LCP = 0 + 1 + 2 + 3 = 6$ . "aaaa" ke distinct substrings hain a, aa, aaa, aaaa = 4. Formula: $\sum (n - S A [r]) - \sum LCP = (1 + 2 + 3 + 4) - 6 = 10 - 6 = 4$ . ✅

Ex 3 — Cell C: sab characters distinct

Ex 4 — Cells D & E: length 1 aur empty (degenerate)

Worked example Do edge inputs ek saath

Forecast: $n = 1$ ke liye, kya LCP array mein koi entry hai? $n = 0$ ke liye, kya koi loop chalta hai?

Case D — $s = "a"$ , $n = 1$ . Kyun care karein? Ek suffix ka matlab hai koi adjacent pair nahi, toh compute karne ke liye koi LCP entry nahi hai.

$S A = [0]$ (sirf wahi suffix).
$rank = [0]$ .
$LCP = [0]$ by convention ( $LCP [0] = 0$ hamesha; koi $r = 1$ entry nahi hai).
Distinct substrings: $\sum (n - S A [r]) - \sum_{r \geq 1} LCP = (1 - 0) - 0 = 1$ . Sahi: sirf "a".

Case E — $s = ""$ , $n = 0$ . Kyun care karein? Classic crash. Har loop for i in range(n) simply execute nahi hona chahiye.

$S A = []$ , $rank = []$ , $LCP = []$ .
Distinct substrings $= 0$ (empty sum).

Verify: $n = 1$ mein 1 distinct substring hai; $n = 0$ mein 0. ✅

Ex 5 — Cell F: Kasai ka "drop by at most 1" reuse dekhna

Worked example Kasai ko

$s = "aab"$ , $n = 3$ par chalao, aur $h$ dekho Forecast: Do consecutive $i$ -steps ke beech mein, $h$ kitna gir sakta hai? Maximum guess karo.

Pehle humein $S A$ chahiye. Suffixes: 0 aab, 1 ab, 2 b. Sorted: aab < ab < b. $S A = [0, 1, 2], rank = [0, 1, 2]$

Step 1 — $i = 0$ , rank $0$ : koi predecessor nahi. Kyun? Suffix aab sorted order mein pehla hai. Set karo $h = 0$ , $LCP [0] = 0$ . Phir $h \leftarrow max (0 - 1, 0) = 0$ .

Step 2 — $i = 1$ , rank $1$ : predecessor $= S A [0] = 0$ . Kyun? Compare karo $suf (1) = ab$ aur $suf (0) = aab$ . Match karo a (pos 0), phir b vs a mismatch → $h = 1$ . Set karo $LCP [1] = 1$ . Phir $h \leftarrow max (1 - 1, 0) = 0$ .

Step 3 — $i = 2$ , rank $2$ : predecessor $= S A [1] = 1$ . Kyun? Compare karo $suf (2) = b$ aur $suf (1) = ab$ . Pehla char b vs a mismatch → $h = 0$ . Set karo $LCP [2] = 0$ .

$LCP = [0, 1, 0]$

Reuse in action: $h = 1$ se Step 3 se pehle carried $h = 0$ tak ki drop exactly 1 thi — kabhi zyada nahi. Woh guaranteed cap hi reason hai ki total work $O (n)$ hai: har character index ko sirf bounded number of times "re-scan" kiya ja sakta hai.

Verify: $LCP = [0, 1, 0]$ , aur distinct substrings $= (3 + 2 + 1) - (0 + 1 + 0) = 6 - 1 = 5$ : a, aa, aab, ab, b. ✅

Ex 6 — Cell G: word problem, pattern search

Worked example Real task:

"banana" mein "an" kitni baar aata hai? Forecast: Sab matches suffix array ka ek contiguous block mein hote hain. Guess karo woh block kitna bada hai.

Parent se: $S A = [5, 3, 1, 0, 4, 2]$ banana ke liye, yaani sorted suffixes

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

Step 1 — ek match = ek suffix jiska prefix "an" hai. Yeh step kyun? $s$ mein pattern $p$ ki har occurrence ek suffix hai jo $p$ se start hoti hai. Kyunki suffixes sorted hain, woh ek contiguous run banate hain — binary-searchable.

Step 2 — prefix "an" ka lower aur upper bound binary search karo. Yeh step kyun? Hum pehla sorted suffix $\geq$ "an" chahte hain aur pehla $>$ "an\xff" (kuch bhi "an…" block se thoda aage).

Lower bound: "ana" at $r = 1$ (yeh $\geq$ "an" hai).
Upper bound: "banana" at $r = 3$ pehla hai jo "an" se start nahi hota.
Toh block hai $r \in {1, 2}$ .

Step 3 — occurrences padhna. Block size $= 2$ . Starting positions $S A [1] = 3$ aur $S A [2] = 1$ . banana → b a n a n a; positions 1 (anana) aur 3 (banana). 2 occurrences.

Verify: banana ko haath se scan karo, an index 1 aur index 3 par aata hai. Count $= 2$ . ✅

Ex 7 — Cell H: distinct substrings count karna (formula drill)

Worked example

$s = "abab"$ ke distinct substrings, $n = 4$ Forecast: abab clearly bahut zyada repeat karta hai. Kya distinct count 10 (sab) ke kareeb hoga ya 6 ke?

Step 1 — $S A$ banao. Suffixes: 0 abab, 1 bab, 2 ab, 3 b. Sorted: ab < abab < b < bab. $S A = [2, 0, 3, 1]$

Step 2 — LCP banao.

$r = 1$ : ab vs abab share ab → $LCP [1] = 2$ .
$r = 2$ : abab vs b kuch share nahi karte → $LCP [2] = 0$ .
$r = 3$ : b vs bab share b → $LCP [3] = 1$ . $LCP = [0, 2, 0, 1]$

Step 3 — counting formula apply karo. Yeh formula kyun? $\sum_{r} (n - S A [r])$ sab substrings count karta hai (har suffix apne length-many prefixes contribute karta hai). $\sum LCP$ unhe remove karta hai jo twice count hue kyunki adjacent suffixes ne ek prefix share kiya tha. $# distinct = \sum_{r} (n - S A [r]) - \sum_{r \geq 1} LCP [r]$ $= [(4 - 2) + (4 - 0) + (4 - 3) + (4 - 1)] - (2 + 0 + 1) = (2 + 4 + 1 + 3) - 3 = 10 - 3 = 7$

Verify: list karo — a, ab, aba, abab, b, ba, bab = 7. ✅ (10 se zyada 6 ke kareeb — repetition distinctness khaata hai.)

Ex 8 — Cell I: exam twist, do non-adjacent suffixes ka LCP

Worked example

"banana" mein $suf (0)$ aur $suf (2)$ ka Longest common prefix Forecast: Woh $S A$ mein neighbors NAHI hain. Toh LCP array akele direct answer nahi deta. Value guess karo, phir trick dekho.

Yaad karo $S A = [5, 3, 1, 0, 4, 2]$ , $rank = [3, 2, 5, 1, 4, 0]$ , $LCP = [0, 1, 3, 0, 0, 2]$ .

Step 1 — dono suffixes ko sorted order mein locate karo. Yeh step kyun? Kisi bhi do suffixes ka LCP unke beech sorted-order stretch par minimum LCP ke barabar hota hai. Toh pehle unke ranks dhundho.

$rank [0] = 3$ (suffix banana).
$rank [2] = 5$ (suffix nana).

Step 2 — LCP ka range minimum lo. Yeh step kyun? Sorted order mein rank 3 se rank 5 tak chalte hue, har adjacent pair sirf utna share karta hai jitna uska LCP hai; endpoints ka shared prefix us raaste ke sabse chhote LCP se lamba nahi ho sakta. Yeh ek range-minimum query hai → Sparse Table use karo. $LCP of two suffixes = min (LCP [4], LCP [5]) = min (0, 2) = 0$ (Hum LCP indices $rank + 1 \dots rank$ of larger par lete hain, yaani $r = 4$ aur $r = 5$ .)

Step 3 — interpret karo. LCP $= 0$ : banana (b se shuru) aur nana (n se shuru) koi prefix share nahi karte.

Verify: banana vs nana — pehle chars b ≠ n. Common prefix length $= 0$ . ✅

Recall RMQ kyun, fresh scan kyun nahi?

Ek fresh character-by-character compare $O (n)$ per query hai. LCP array plus RMQ ke saath $O (n lo g n)$ mein precompute karke, har "LCP of two suffixes" query $O (1)$ ho jaati hai. Yahi LCP array ka poora payoff hai.

Recap

Recall Har example ne kaun sa cell cover kiya?

Ex 1 ::: A — generic string, full prefix-doubling Ex 2 ::: B — sab equal characters (staircase LCP) Ex 3 ::: C — sab distinct (ek round, zero LCP) Ex 4 ::: D aur E — length 1 aur empty string Ex 5 ::: F — Kasai ka $h$ carry-over, drop-by-1 Ex 6 ::: G — pattern search via contiguous block Ex 7 ::: H — distinct-substring counting formula Ex 8 ::: I — non-adjacent suffixes ka LCP via RMQ

Related tools jo revisit karne layak hain: Radix Sort aur Counting Sort (fast per-round sorting), Suffix Tree (bhaari cousin), Z-Algorithm aur KMP (single-pattern alternatives), aur Burrows–Wheeler Transform (sorted-suffix order se directly banta hai).