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

True or false — justify

Every string of length

n

has a suffix array that is a permutation of

{0, \dots, n - 1}

True — there are exactly

n

suffixes, all start at distinct indices, and each appears once in sorted order, so

S A

is always a bijection on

{0, \dots, n - 1}

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

False — suffixes have different lengths (they start at different indices), so no two are identical; the shorter one is a strict prefix of the longer at most, and a prefix always sorts strictly before.

LCP [r]

measures the shared prefix of suffixes starting at index

r

and index

r + 1

False — it is the LCP of the sorted neighbours

suf (S A [r - 1])

and

suf (S A [r])

; the indices

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

can be anywhere in the string, not

r

and

r + 1

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

means they share no leading character, so their first letters differ (this is exactly the boundary between "letter blocks" in

S A

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

True — rank is the inverse permutation of

S A

(

rank [S A [r]] = r

), so either one reconstructs the other in

O (n)

; they are two views of the same ordering.

Prefix-doubling needs exactly

lo g_{2} n

rounds regardless of the string.

True (up to ceiling) —

k

doubles

1, 2, 4, \dots

until

k \geq n

, so it always takes

⌈ lo g_{2} n ⌉

rounds; the string's content changes the ranks but never the number of rounds.

Kasai's algorithm processes suffixes in sorted (

S A

) order.

False — it walks indices

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

in string order; that ordering is what makes the "

h

drops by at most 1" reuse valid.

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])

counts every prefix of every suffix (all substrings with multiplicity), and each

LCP [r]

subtracts exactly the substrings duplicated between sorted neighbours.

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

O (1)

True — the LCP of

suf (S A [a])

and

suf (S A [b])

equals the minimum of

LCP [a + 1.. b]

, which a Sparse Table / RMQ answers in

O (1)

after

O (n lo g n)

preprocessing.

Spot the error

"To compare two suffixes on their first

2 k

chars I need to compare

2 k

characters directly."

Wrong — the whole point of doubling is you glue two known

k

-rank halves: the key is the pair

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

, so each comparison is

O (1)

, not

O (k)

"For

i + k \geq n

I'll use

r_{k} [i + k] = 0

since there's nothing there."

Wrong —

0

is a valid rank, so a suffix that ran off the end would tie/outrank a real suffix; use

- 1

(smaller than every real rank) to encode that end-of-string is lexicographically smallest.

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

O (n lo g n)

Wrong — a comparison sort is

O (n lo g n)

per round over

lo g n

rounds

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

; only Radix Sort (or Counting Sort) per round gives true

O (n lo g n)

"In Kasai I reset

h = 0

at the start of every

i

to be safe."

Wrong — that throws away the amortization and makes it

O (n^{2})

; you must carry

h

across iterations, only doing

h \leftarrow max (h - 1, 0)

before each step.

"After radix-sorting pairs I can reuse the same

r_{k}

array in place while assigning

r_{2 k}

Wrong — you need old ranks to detect ties while assigning new ones; overwrite before all comparisons finish and equal pairs get different ranks, corrupting the order. Use a separate temp array.

LCP [0]

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

Wrong —

LCP [0]

has no predecessor so it is defined as

0

by convention; it is not a wrap-around comparison.

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

Wrong — all suffixes with a given prefix are consecutive in sorted order, so occurrences of a pattern always form a contiguous block of

S A

(that's why Binary Search on Suffix Array works).

Why questions

Why does sorting by the pair

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

correctly give the order by first

2 k

characters?

Because the first

2 k

chars of suffix

i

split as (first

k

of suffix

i

) followed by (first

k

of suffix

i + k

); lexicographic order on that concatenation is exactly lexicographic order on the pair of their ranks.

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

Because a shorter suffix that is a prefix of a longer one must sort first (like "an" before "ana" in a dictionary), and modelling the missing character as the smallest possible value enforces exactly that rule.

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

i

i + 1

suf (i)

h

chars with its predecessor

suf (j)

, then

suf (i + 1)

and

suf (j + 1)

h - 1

and

suf (j + 1)

still sorts before

suf (i + 1)

, so the true predecessor of

i + 1

shares at least

h - 1

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

The array is a flat integer array — far smaller constant-factor memory and much simpler to implement — giving most of the tree's query power (substring search, repeats, distinct counts) at a fraction of the pain.

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

S A

We visit suffixes by starting index

i

and must instantly find where

i

sits in sorted order to get its predecessor

S A [rank [i] - 1]

; only the inverse permutation rank gives that in

O (1)

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

Sorted neighbours share their first

LCP [r]

prefixes, so those

LCP [r]

substrings of the later suffix were already counted by the earlier one; subtracting them removes the double-counting precisely once.

Edge cases

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

S A = [0]

— there is exactly one suffix, and the LCP array is just

[0]

(no adjacent pair exists to compare).

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

Suffixes sort by length (

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

) and each neighbour shares everything but the extra leading char, so

LCP = [0, 1, 2, 3]

— the maximal staircase.

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

All

LCP [r] = 0

for

r \geq 1

— no two suffixes share a first character once sorted, so neighbours have no common prefix.

How many doubling rounds run when

n = 1

Zero effective rounds beyond the initial single-character ranking, since

k = 1 \geq n = 1

already; the initial rank is the final order.

What happens in Kasai when

rank [i] = 0

(suffix

i

is the smallest)?

It has no sorted predecessor, so we set

h = 0

and record nothing extra; the next

i

simply starts fresh from this floor.

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

It adds one shortest suffix that sorts first and guarantees no suffix is a prefix of another, which simplifies proofs and some constructions without disturbing the relative order of the original suffixes.

Recall One-line self-test before you leave

Can you state, without peeking: (1) whose two suffixes $LCP [r]$ compares, (2) why the off-end rank is $- 1$ , (3) why $h$ must be carried in Kasai, and (4) why doubling gives $lo g n$ rounds? If any is fuzzy, reread that trap above.