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

This is the hands-on companion to the parent Suffix-Array note. The parent built the machinery; here we run that machinery across every kind of input a problem can hand you — including the weird degenerate ones that break naive code.

The scenario matrix

Every string you will ever feed a suffix array falls into one of these cells. The final column names the example that pins it down.

Cell	Scenario class	What could break	Example
A	Generic mixed string	prefix-doubling rounds, sentinel $- 1$	Ex 1 (`mississippi`)
B	All characters equal (`aaaa`)	every suffix shares a prefix; LCP is a staircase	Ex 2
C	All characters distinct (`abcd`)	first round already finishes; LCP all zero	Ex 3
D	Length 1 (`a`)	one suffix, no adjacent pair, no LCP entry	Ex 4
E	Empty string ( $n = 0$ )	loops must not run; array is empty	Ex 4
F	Kasai "drop by at most 1" reuse	resetting $h$ wrongly → $O (n^{2})$	Ex 5
G	Word problem — pattern search	binary-search block must be contiguous	Ex 6
H	Counting distinct substrings via LCP	off-by-one in the two sums	Ex 7
I	Exam twist — two suffixes' LCP via RMQ	LCP of non-adjacent pair needs a range-min	Ex 8

Cells A–I are all covered below. Let us walk them.

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

Worked example Build

$S A$ for $s = "mississippi"$ , $n = 11$ Forecast: Guess where suffix "i" (index 10) lands. Smallest? Somewhere in the middle? Write your guess before reading.

The 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$ , sort by first letter. Why this step? We know nothing yet, so we only trust one character. Alphabet order of the letters present: i < m < p < s. Assign ranks i→0, m→1, p→2, s→3. $r_{1} = [1, 0, 3, 3, 0, 3, 3, 0, 2, 2, 0]$ (read off letter of each index: m,i,s,s,i,s,s,i,p,p,i).

Step 2 — round $k = 2$ , key $= (r_{1} [i], r_{1} [i + 2])$ . Why this step? Two characters distinguish suffixes that tied on one. For $i + 2 \geq 11$ we use the sentinel $- 1$ (end-of-string is smaller than any letter — see the parent's mistake box).

Step 3 — keep doubling $k = 4, 8$ . Since $⌈ lo g_{2} 11 ⌉ = 4$ , after four rounds ( $k = 1, 2, 4, 8$ ) $k \geq n$ and ranks are final.

Result: $S A = [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2]$ So suffix "i" (index 10) is the smallest — it sorts first. Did your forecast match?

Verify: the first four sorted suffixes are i < ippi < issippi < ississippi — each is a prefix of or lexicographically below the next. ✅ Sorted correctly (checked in VERIFY).

Ex 2 — Cell B: all characters equal

Ex 3 — Cell C: all characters distinct

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

Worked example Two edge inputs at once

Forecast: For $n = 1$ , does the LCP array have any entries? For $n = 0$ , do any loops run?

Case D — $s = "a"$ , $n = 1$ . Why care? One suffix means no adjacent pair, so there is no LCP entry to compute.

$S A = [0]$ (the only suffix).
$rank = [0]$ .
$LCP = [0]$ by convention ( $LCP [0] = 0$ always; there is no $r = 1$ entry).
Distinct substrings: $\sum (n - S A [r]) - \sum_{r \geq 1} LCP = (1 - 0) - 0 = 1$ . Correct: only "a".

Case E — $s = ""$ , $n = 0$ . Why care? The classic crash. Every loop for i in range(n) must simply not execute.

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

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

Ex 5 — Cell F: watching Kasai's "drop by at most 1" reuse

Worked example Run Kasai on

$s = "aab"$ , $n = 3$ , and watch $h$ Forecast: Between two consecutive $i$ -steps, how much can $h$ fall? Guess the maximum.

First we need $S A$ . 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$ : no predecessor. Why? Suffix aab is first in sorted order. Set $h = 0$ , $LCP [0] = 0$ . Then $h \leftarrow max (0 - 1, 0) = 0$ .

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

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

$LCP = [0, 1, 0]$

The reuse in action: the drop from $h = 1$ to the carried $h = 0$ before Step 3 was exactly 1 — never more. That guaranteed cap is why the total work is $O (n)$ : each character index can only be "re-scanned" a bounded number of times.

Verify: $LCP = [0, 1, 0]$ , and 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: how many times does

"an" occur in "banana"? Forecast: All matches sit in one contiguous block of the suffix array. Guess how big that block is.

From the parent: $S A = [5, 3, 1, 0, 4, 2]$ for banana, i.e. 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 — a match = a suffix whose prefix is "an". Why this step? Every occurrence of pattern $p$ in $s$ is a suffix that starts with $p$ . Because suffixes are sorted, those form one contiguous run — binary-searchable.

Step 2 — binary search the lower and upper bound of prefix "an". Why this step? We want the first sorted suffix $\geq$ "an" and the first $>$ "an\xff" (anything just past the "an…" block).

Lower bound: "ana" at $r = 1$ (it is $\geq$ "an").
Upper bound: "banana" at $r = 3$ is the first not starting with "an".
So the block is $r \in {1, 2}$ .

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

Verify: scanning banana by hand, an appears at index 1 and index 3. Count $= 2$ . ✅

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

Worked example Distinct substrings of

$s = "abab"$ , $n = 4$ Forecast: abab clearly repeats a lot. Will distinct count be closer to 10 (all) or to 6?

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

Step 2 — build LCP.

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

Step 3 — apply the counting formula. Why this formula? $\sum_{r} (n - S A [r])$ counts all substrings (each suffix contributes its length-many prefixes). $\sum LCP$ removes the ones counted twice because adjacent suffixes shared a prefix. $# 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 them — a, ab, aba, abab, b, ba, bab = 7. ✅ (Closer to 6 than 10 — repetition costs distinctness.)

Ex 8 — Cell I: exam twist, LCP of two non-adjacent suffixes

Worked example Longest common prefix of

$suf (0)$ and $suf (2)$ in "banana" Forecast: They are NOT neighbors in $S A$ . So the LCP array alone doesn't give the answer directly. Guess the value, then see the trick.

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

Step 1 — locate both suffixes in sorted order. Why this step? The LCP of any two suffixes equals the minimum LCP over the sorted-order stretch between them. So first find their ranks.

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

Step 2 — take the range minimum of LCP. Why this step? Walking from rank 3 to rank 5 in sorted order, each adjacent pair shares only as much as its LCP; the shared prefix of the endpoints can be no longer than the smallest LCP along the way. This is a range-minimum query → use a Sparse Table. $LCP of two suffixes = min (LCP [4], LCP [5]) = min (0, 2) = 0$ (We take LCP over indices $rank + 1 \dots rank$ of the larger, i.e. $r = 4$ and $r = 5$ .)

Step 3 — interpret. LCP $= 0$ : banana (starts b) and nana (starts n) share no prefix.

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

Recall Why RMQ and not a fresh scan?

A fresh character-by-character compare is $O (n)$ per query. With the LCP array plus RMQ precomputed in $O (n lo g n)$ , each "LCP of two suffixes" query drops to $O (1)$ . That is the whole payoff of the LCP array.

Recap

Recall Which cell did each example cover?

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

Related tools worth revisiting: Radix Sort and Counting Sort (fast per-round sorting), Suffix Tree (the heavier cousin), Z-Algorithm and KMP (single-pattern alternatives), and Burrows–Wheeler Transform (built directly from the sorted-suffix order).