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

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

Intuition Is page ko kaise use karein

Har problem apne aap mein complete hai. Pehle solution ko cover karo, khud try karo, phir reveal karo. Difficulty badhti jaati hai: L1 Recognition (kya tum array padh sakte ho?) → L2 Application (ek algorithm chalao) → L3 Analysis (ye kaam kyun karta hai / edge cases) → L4 Synthesis (ideas ko combine karo) → L5 Mastery (design / prove). Yahan sab kuch parent note pe build karta hai — agar koi symbol unfamiliar lage, toh woh wahan define hai.

Notation ka reminder (taaki pehli line readable ho):

$s$ = length $n$ ki ek string, indexed $0.. n - 1$ .
$suf (i) = s [i .. n - 1]$ = string ki "tail" jo position $i$ se start hoti hai.
$S A [r]$ = $r$ -th smallest tail ka starting index (dictionary order mein).
$rank [i]$ = tail $i$ us sorted list mein kahan hai ( $S A$ ka inverse).
$LCP [r]$ = tails $S A [r - 1]$ aur $S A [r]$ ke kitne pehle letters common hain.

Level 1 — Recognition

Recall Solution L1.1

Chaaron tails ko dictionary order mein rakho. Letter by letter compare karo:

$ab$ (index 2 se) vs $abab$ (index 0): dono ab pe agree karte hain, phir abab continue karta hai jabki ab khatam ho jaati hai. Jo string khatam hoti hai woh chhoti hoti hai (shorter prefix wins). Toh $ab < abab$ .
Dono a-se-start hone waali tails dono b-se-start hone waali tails se pehle aati hain.
b mein se: $b$ (index 3) vs $bab$ (index 1): b pehle khatam hoti hai → chhoti. Toh $b < bab$ .

Sorted: $ab (2) < abab (0) < b (3) < bab (1)$ . $S A = [2, 0, 3, 1]$

Recall Solution L1.2

$rank$ inverse permutation hai: $rank [S A [r]] = r$ . $r = 0..3$ walk karo:

$S A [0] = 2 \Rightarrow rank [2] = 0$
$S A [1] = 0 \Rightarrow rank [0] = 1$
$S A [2] = 3 \Rightarrow rank [3] = 2$
$S A [3] = 1 \Rightarrow rank [1] = 3$

$rank = [1, 3, 0, 2]$

Level 2 — Application

Recall Solution L2.1

Do "first-1-letter" answers se "first-2-letters" glue karo. End ke baad $\to - 1$ :

i=0: (r1[0], r1[2]) = (0, 0)
i=1: (r1[1], r1[3]) = (1, 1)
i=2: (r1[2], -1)    = (0, -1)
i=3: (r1[3], -1)    = (1, -1)

Pairs ko ascending sort karo (pehle first component compare karo, phir second): $(0, - 1) \to i = 2$ , $(0, 0) \to i = 0$ , $(1, - 1) \to i = 3$ , $(1, 1) \to i = 1$ . $S A = [2, 0, 3, 1]$ L1.1 se exactly match karta hai — do characters ne in suffixes ko puri tarah separate kar diya, toh ye round final hai. (Pair components ke liye Radix Sort / Counting Sort use karo $O (n)$ per round ke liye.)

Recall Solution L2.2

Starting index $i$ se walk karo, predecessor $j = S A [rank [i] - 1]$ , $h$ extend karo jab $s [i + h] = s [j + h]$ , phir $h \leftarrow max (h - 1, 0)$ :

i=0 rank=1 pred=SA[0]=2: suf0=abab vs suf2=ab -> match "ab"=2. LCP[1]=2. h=1
i=1 rank=3 pred=SA[2]=3: suf1=bab  vs suf3=b  -> match "b" =1. LCP[3]=1. h=0
i=2 rank=0 : no predecessor -> h=0
i=3 rank=2 pred=SA[1]=0: suf3=b    vs suf0=abab -> match ""=0. LCP[2]=0. h=0

Sorted position ke hisaab se store karo, convention se $LCP [0] = 0$ : $LCP = [0, 2, 0, 1]$ Padho isko: neighbors $S A [0] = 2, S A [1] = 0$ (ab,abab) 2 share karte hain; $S A [1] = 0, S A [2] = 3$ (abab,b) 0 share karte hain; $S A [2] = 3, S A [3] = 1$ (b,bab) 1 share karte hain. ✅

Level 3 — Analysis

Recall Solution L3.1

Saare suffixes ke upar total prefixes: $\sum (n - S A [r]) = (4 - 2) + (4 - 0) + (4 - 3) + (4 - 1) = 2 + 4 + 1 + 3 = 10$ .
Double-counted overlaps: $\sum_{r \geq 1} LCP [r] = 2 + 0 + 1 = 3$ .
Distinct $= 10 - 3 = 7$ .

Sanity list: length-1 a,b; length-2 ab,ba; length-3 aba,bab; length-4 abab. Yani $2 + 2 + 2 + 1 = 7$ . ✅

Recall Solution L3.2

Suffix $i$ ke characters khatam ho gaye hain — uski true tail chhoti hai. Ek chhoti string jo doosre ki prefix hai woh dictionary order mein pehle aani chahiye. Rule $r_{k} [i + k] = - 1$ set karta hai aur $r_{k} [j + k] = 0$ rakhta hai. Kyunki $- 1 < 0$ , pair $(\cdot, - 1)$ pair $(\cdot, 0)$ se pehle sort hota hai, suffix $i$ ko pehle place karta hai. ✅ Correct. Agar hum off-end ke liye $0$ (ya garbage) use karte, toh tie arbitrarily break hoti aur lambe suffix ko pehle place kar sakti thi — ek bug. Sentinel encode karta hai "end-of-string kisi bhi letter se chhota hai".

Recall Solution L3.3

$k$ chalti hai $1, 2, 4, 8, \dots$ . Hum tab rukते hain jab $k \geq 1000$ : $2^{9} = 512 < 1000 \leq 1024 = 2^{10}$ . Toh hume $k = 1024$ chahiye, 10 doublings ke baad reach hota hai $k = 1$ se ( $1 \to 2 \to 4 \to 8 \to 16 \to 32 \to 64 \to 128 \to 256 \to 512 \to 1024$ ). Ye $⌈ lo g_{2} n ⌉ = ⌈ lo g_{2} 1000 ⌉ = 10$ hai. Har round $O (n)$ hai radix sort ke saath → total $O (n lo g n)$ .

Level 4 — Synthesis

Recall Solution L4.1

$max LCP = 3$ , $r = 2$ pe. Toh sabse lamba repeated substring ki length $3$ hai, $S A [2] = 1$ se start hota hai: $s [1..3] = "ana" .$ Check karo: ana index 1 pe aata hai (b**ana**na) aur index 3 pe (ban**ana**). ✅ LCP kyun find karta hai: ek repeated substring do alag suffixes ka common prefix hai; saare pairs mein sabse bada aisa common prefix kisi adjacent pair ke dwara achieve hota hai sorted order mein (sorting similar tails ko cluster karti hai), aur yahi LCP array record karta hai. Figure dekho.

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

Recall Solution L4.2

Kyunki $S A$ tails ko dictionary order mein list karta hai, na se start hone wali har tail ek saath hoti hai. Sorted tails hain:

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

Wo tails jinki prefix na hai: rows $r = 4$ (na) aur $r = 5$ (nana). Block $= [4, 5]$ , toh na 2 baar aata hai, positions $S A [4] = 4$ aur $S A [2 ’s row] = 2$ pe, yani indices ${4, 2}$ . Do binary searches (lower + upper bound) is block ko $O (∣ p ∣ lo g n)$ mein find karte hain.

Level 5 — Mastery

Recall Solution L5.1

$rank [1] = 2$ , $rank [3] = 1$ . Inhe order karo: chhota rank $= 1$ (suffix 3), bada $= 2$ (suffix 1). Range hai $r \in {2}$ (yani $r$ $1 + 1$ se $2$ tak): $min {LCP [2]} = min {3} = 3$ . Direct check: $suf (1) = anana$ , $suf (3) = ana$ ana share karte hain (length 3). ✅ Min kyun: sorted order mein rank $a$ se rank $b$ tak chalte hue, shared prefix sirf shrink ya same reh sakta hai — har adjacent step mein $LCP$ mein recorded difference se zyada nahi hatega. Sabse tight bottleneck minimum hai. Woh min-over-a-range query $O (n lo g n)$ preprocessing ke baad sparse table se $O (1)$ mein answer hoti hai.

Recall Solution L5.2

$s = "aa"$ ke liye: tails aa(0), a(1). Sorted: a(1) < aa(0), toh $S A = [1, 0]$ . $LCP [1] =$ LCP(a,aa) $= 1$ . Distinct $= \sum (n - S A [r]) - \sum LCP = [(2 - 1) + (2 - 0)] - 1 = (1 + 2) - 1 = 2$ . Check: aa ke distinct substrings hain a,aa → 2. ✅ $s = "aaa"$ ke liye: $S A = [2, 1, 0]$ (a<aa<aaa), $LCP = [0, 1, 2]$ . Distinct $= [(3 - 2) + (3 - 1) + (3 - 0)] - (1 + 2) = (1 + 2 + 3) - 3 = 6 - 3 = 3$ . Check: a,aa,aaa → 3. ✅ Insight: yahan ek repeated character append karne se exactly ek naya distinct substring add hota hai (poora naya run), kyunki har chhota run already exist karta tha. $m$ identical letters ki string mein exactly $m$ distinct substrings hote hain.

Recall Solution L5.3

Maano $suf (i)$ ka predecessor $suf (j)$ sorted order mein $h \geq 1$ characters share karta hai. Kyunki $s [i] = s [j]$ , pehla char drop karne se $suf (i + 1)$ aur $suf (j + 1)$ milte hain jo $h - 1$ characters share karte hain, aur importantly $suf (j + 1)$ abhi bhi $suf (i + 1)$ se pehle sort hota hai (equal leading char hatana order preserve karta hai). $suf (i + 1)$ ka true predecessor kam se kam $suf (j + 1)$ jitna close hai, toh woh kam se kam $h - 1$ chars share karta hai. Isliye scan $h - 1$ se start karna kabhi overshoot nahi karta. Cost bound: while-loop character matches ki sankhya se $h$ increase hota hai aur har step mein at most $1$ se decrease. $n$ steps ke upar total decrease $\leq n$ , toh total increase $\leq n + h_{final} \leq 2 n$ . Isliye combined match work $O (n)$ hai — linear. ∎

Recall Har level ka one-line recap

L1 ::: $S A$ (sorted tail indices) padho aur use $rank$ mein invert karo; string-end sabse chhota hota hai. L2 ::: Ek doubling round rank-pairs glue karta hai; Kasai index ke hisaab se $h$ carry karta hua walk karta hai. L3 ::: Distinct $= \sum (n - S A [r]) - \sum LCP$ ; $- 1$ sentinel chhote suffixes ko pehle force karta hai. L4 ::: $max LCP$ = longest repeated substring; pattern hits ek contiguous $S A$ block banate hain. L5 ::: Kisi bhi pair ka LCP = $LCP$ ka range-min; Kasai $O (n)$ hai drop-by-one lemma se.