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

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

True or false — justify

Every string of length

n

has a suffix array that is a permutation of

{0, \dots, n - 1}

True — exactly

n

suffixes hote hain, sab alag-alag indices pe start hote hain, aur har ek sorted order mein ek baar aata hai, isliye

S A

hamesha

{0, \dots, n - 1}

par ek bijection hota hai.

Two different suffixes of the same string can be exactly equal, so the sorted order has ties.

False — suffixes ki lengths alag hoti hain (woh alag indices pe start hote hain), isliye koi bhi do exactly identical nahi ho sakte; chhota wala zyada se zyada lambe ka strict prefix ho sakta hai, aur prefix hamesha strictly pehle sort hota hai.

LCP [r]

measures the shared prefix of suffixes starting at index

r

and index

r + 1

False — yeh sorted neighbours

suf (S A [r - 1])

aur

suf (S A [r])

ka LCP hai; indices

S A [r - 1], S A [r]

string mein kahin bhi ho sakte hain,

r

aur

r + 1

pe nahi necessarily.

LCP [r] = 0

for some

r

, then

suf (S A [r - 1])

and

suf (S A [r])

start with different first characters.

True — LCP

= 0

ka matlab hai koi bhi leading character share nahi hota, isliye unke pehle letters differ karte hain (yahi

S A

mein "letter blocks" ke beech boundary hai).

The rank array and the suffix array contain the same information.

True — rank,

S A

ki inverse permutation hai (

rank [S A [r]] = r

), isliye dono ek-doosre ko

O (n)

mein reconstruct kar sakte hain; yeh usi ordering ke do views hain.

Prefix-doubling needs exactly

lo g_{2} n

rounds regardless of the string.

True (ceiling tak) —

k

double hota hai

1, 2, 4, \dots

jab tak

k \geq n

na ho, isliye hamesha

⌈ lo g_{2} n ⌉

rounds lagte hain; string ka content ranks change karta hai lekin rounds ki ginti kabhi nahi.

Kasai's algorithm processes suffixes in sorted (

S A

) order.

False — yeh indices

i = 0, 1, \dots, n - 1

ko string order mein walk karta hai; wahi ordering hai jo "

h

at most 1 se girta hai" reuse ko valid banati hai.

The number of distinct substrings of

s

equals

\sum_{r} (n - S A [r]) - \sum_{r \geq 1} LCP [r]

True —

\sum (n - S A [r])

har suffix ke har prefix ko count karta hai (multiplicity ke saath sab substrings), aur har

LCP [r]

exactly woh substrings subtract karta hai jo sorted neighbours ke beech duplicate hain.

A suffix array plus an LCP array can answer "LCP of any two suffixes" (not just neighbours) in

O (1)

True —

suf (S A [a])

aur

suf (S A [b])

ka LCP

LCP [a + 1.. b]

ka minimum hota hai, jise Sparse Table / RMQ

O (n lo g n)

preprocessing ke baad

O (1)

mein answer karta hai.

Spot the error

"To compare two suffixes on their first

2 k

chars I need to compare

2 k

characters directly."

Wrong — doubling ka poora point yahi hai ki tum do known

k

-rank halves ko jodoge: key hai pair

(r_{k} [i], r_{k} [i + k])

, isliye har comparison

O (1)

hai,

O (k)

nahi.

"For

i + k \geq n

I'll use

r_{k} [i + k] = 0

since there's nothing there."

Wrong —

0

ek valid rank hai, isliye end-of-string pe pahuncha suffix ek real suffix ke saath tie/outrank kar sakta hai; end-of-string ko lexicographically smallest encode karne ke liye

- 1

(har real rank se chhota) use karo.

"Each round of doubling with a comparison sort keeps the total at

O (n lo g n)

Wrong — comparison sort per round

O (n lo g n)

hai,

lo g n

rounds ke upar

= O (n lo g^{2} n)

hota hai; sirf Radix Sort (ya Counting Sort) per round true

O (n lo g n)

deta hai.

"In Kasai I reset

h = 0

at the start of every

i

to be safe."

Wrong — yeh amortization throw away kar deta hai aur ise

O (n^{2})

bana deta hai; tumhe

h

ko iterations ke across carry karna hai, har step se pehle sirf

h \leftarrow max (h - 1, 0)

karo.

"After radix-sorting pairs I can reuse the same

r_{k}

array in place while assigning

r_{2 k}

Wrong — naye ranks assign karte waqt tum ties detect karne ke liye purane ranks chahiye; sab comparisons khatam hone se pehle overwrite karo toh equal pairs ko alag ranks milenge, order corrupt ho jayega. Ek alag temp array use karo.

LCP [0]

is the LCP of the first suffix with the last one."

Wrong —

LCP [0]

ka koi predecessor nahi hai isliye convention se yeh

0

define hota hai; yeh wrap-around comparison nahi hai.

"Since suffixes overlap, binary-searching a pattern might match a non-contiguous set of positions."

Wrong — kisi given prefix wale sab suffixes sorted order mein consecutive hote hain, isliye pattern ki occurrences hamesha

S A

ka ek contiguous block banati hain (isliye hi Binary Search on Suffix Array kaam karta hai).

Why questions

Why does sorting by the pair

(r_{k} [i], r_{k} [i + k])

correctly give the order by first

2 k

characters?

Kyunki suffix

i

ke pehle

2 k

chars split hote hain (suffix

i

ke pehle

k

) aur phir (suffix

i + k

ke pehle

k

) ke roop mein; us concatenation par lexicographic order exactly unke ranks ke pair par lexicographic order hai.

Why is end-of-string treated as smaller than every real character?

Kyunki ek chhota suffix jo lambe ka prefix hai woh pehle sort hona chahiye (jaise dictionary mein "an" "ana" se pehle), aur missing character ko sabse chhoti possible value model karna exactly wahi rule enforce karta hai.

Why does the LCP with the sorted predecessor drop by at most 1 when moving from index

i

i + 1

Agar

suf (i)

apne predecessor

suf (j)

ke saath

h

chars share karta hai, toh

suf (i + 1)

aur

suf (j + 1)

h - 1

share karte hain aur

suf (j + 1)

phir bhi

suf (i + 1)

se pehle sort hota hai, isliye

i + 1

ka true predecessor kam se kam

h - 1

share karta hai.

Why is a suffix array often preferred over a Suffix Tree despite the tree being "more powerful"?

Array ek flat integer array hai — bahut chhota constant-factor memory aur implement karna kaafi simple — tree ki zyaadatar query power (substring search, repeats, distinct counts) deta hai bahut kam takleef mein.

Why do we need the rank array inside Kasai rather than just

S A

Hum suffixes ko starting index

i

se visit karte hain aur instantly jaanna chahte hain ki

i

sorted order mein kahaan hai taaki uska predecessor

S A [rank [i] - 1]

mil sake; sirf inverse permutation rank yeh

O (1)

mein deta hai.

Why does distinct-substring counting subtract exactly the LCP values?

Sorted neighbours apne pehle

LCP [r]

prefixes share karte hain, isliye baad wale suffix ke woh

LCP [r]

substrings pehle waale ne already count kar liye the; unhe subtract karna double-counting exactly ek baar remove karta hai.

Edge cases

What is the suffix array of a single-character string like "z"?

S A = [0]

— exactly ek suffix hai, aur LCP array sirf

[0]

hai (compare karne ke liye koi adjacent pair nahi hai).

What does the LCP array look like for a string of all identical characters, e.g. "aaaa"?

Suffixes length ke hisaab se sort hote hain (

S A = [3, 2, 1, 0]

) aur har neighbour extra leading char ko chhodkar sab kuch share karta hai, isliye

LCP = [0, 1, 2, 3]

— maximum staircase.

For a string of all distinct characters like "abcd", what is every LCP value?

Sab

LCP [r] = 0

hote hain

r \geq 1

ke liye — sort hone ke baad koi bhi do suffixes pehla character share nahi karte, isliye neighbours ka koi common prefix nahi.

How many doubling rounds run when

n = 1

Initial single-character ranking ke baad zero effective rounds, kyunki

k = 1 \geq n = 1

already hai; initial rank hi final order hai.

What happens in Kasai when

rank [i] = 0

(suffix

i

is the smallest)?

Iska koi sorted predecessor nahi hai, isliye hum

h = 0

set karte hain aur kuch extra record nahi karte; agla

i

simply is floor se fresh start karta hai.

Does appending a unique sentinel character (like $, smaller than all letters) change the suffix array of the rest?

Yeh ek sabse chhota suffix add karta hai jo pehle sort hota hai aur guarantee deta hai ki koi suffix doosre ka prefix nahi hai, jo proofs aur kuch constructions simplify karta hai bina original suffixes ke relative order disturb kiye.

Recall Jaane se pehle ek-line self-test

Kya tum bina dekhe bata sakte ho: (1) $LCP [r]$ kin do suffixes ko compare karta hai, (2) off-end rank $- 1$ kyun hota hai, (3) Kasai mein $h$ carry kyun karna chahiye, aur (4) doubling $lo g n$ rounds kyun deta hai? Agar koi bhi fuzzy lag raha hai, upar woh trap dobara padho.