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

Intuition The big picture (WHY this exists)

A suffix array is just the list of all suffixes of a string, sorted lexicographically, stored as an array of their starting indices.

WHY do we want this? A suffix tree solves the same problems (substring search, longest repeated substring, etc.) but is heavy on memory and fiddly to code. The suffix array gives ~90% of the power at ~20% of the pain — it's a flat integer array. That's the 80/20 win.

WHAT it buys you: any substring of $s$ is a prefix of some suffix. If suffixes are sorted, all occurrences of a pattern $p$ form a contiguous block you can binary-search. Add the LCP array (longest common prefix of adjacent sorted suffixes) and you can count distinct substrings, find longest repeated substrings, and answer "longest common prefix of any two suffixes" in $O(1)$ .

1. Definitions

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

2. Construction in $O(n\log n)$ — derived from scratch

Intuition The trick: sort by doubling (prefix-doubling)

Naively sorting $n$ suffixes by comparing whole strings is $O(n^2\log n)$ — each comparison is $O(n)$ .

Key idea: sort suffixes by only their first $k$ characters, then by their first $2k$ , then $4k$ … After $\log n$ rounds, $k\ge n$ and we've fully sorted.

WHY doubling works (the crux): Suppose after a round we know the rank of every suffix based on its first $k$ chars. Now I want to compare two suffixes on their first $2k$ chars. The first- $2k$ block of suffix $i$ = (first $k$ chars of suffix $i$ ) + (first $k$ chars of suffix $i+k$ ). I already have ranks for both halves! So the comparison key for suffix $i$ is the pair $(\text{rank}_k[i],\ \text{rank}_k[i+k])$ . Sorting pairs is cheap.

HOW the cost comes out to $O(n\log n)$ :

Number of rounds $= \lceil\log_2 n\rceil$ (because $k$ doubles: $1,2,4,\dots,\ge n$ ).
Each round sorts $n$ pairs. With radix sort (two passes on small integer keys $\in[0,n]$ ) each round is $O(n)$ . → total $O(n\log n)$ .
If you use comparison sort each round ( $O(n\log n)$ ), total is $O(n\log^2 n)$ — still fine and far simpler to code.

Worked example Build

$SA$ for $s = \texttt{"banana"}$ ( $n=6$ ) Suffixes & indices:

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

Round k=1 (sort by 1 char): rank by letter. $a<b<n$ . indices sorted: a's then b then n's → ranks $r_1 = [\,1(b),0(a),2(n),0(a),2(n),0(a)\,]$ wait — ties resolved by letter only. Assign: a→0, b→1, n→2. So $r_1=[1,0,2,0,2,0]$ . Why this step? We only know the first letter; all a's tie (rank 0).

Round k=2, key $=(r_1[i], r_1[i+2])$ :

i=0: (1, 2)   i=3: (0, 0)
i=1: (0, 2)   i=4: (2, -1)
i=2: (2, 0)   i=5: (0, -1)

Sort pairs ascending → order of indices: 5(0,-1),3(0,0),1(0,2),0(1,2),2(2,0),4(2,-1). New ranks $r_2=[3,2,4,1,5,0]$ . Why? Two chars now distinguish almost everything; only need one more round.

Round k=4, key $=(r_2[i], r_2[i+4])$ :

i=0:(3,5) i=1:(2,0) i=2:(4,-1) i=3:(1,-1) i=4:(5,-1) i=5:(0,-1)

All keys distinct → final. Sort → $SA=[5,3,1,0,4,2]$ . Check: suf(5)=a, suf(3)=ana, suf(1)=anana, suf(0)=banana, suf(4)=na, suf(2)=nana. ✅ sorted!

3. The LCP array — Kasai's $O(n)$ algorithm, derived

Intuition Why LCP can be built in linear time (the magic observation)

Process suffixes in order of starting index $i=0,1,\dots$ (NOT in sorted order). Let $h$ = LCP of suffix $i$ with its predecessor in sorted order.

Steel-manned claim: when we move from suffix $i$ to suffix $i+1$ , the LCP drops by at most 1.

WHY? Suppose suffix $i$ shares a prefix of length $h\ge 1$ with the suffix $j$ that sits just before it in $SA$ . Then $s[i]=s[j]$ and the remaining parts are $\text{suf}(i+1)$ and $\text{suf}(j+1)$ , which already share a prefix of length $h-1$ , AND $\text{suf}(j+1)$ comes before $\text{suf}(i+1)$ in sorted order. So whatever suffix is the true predecessor of $i+1$ shares at least $h-1$ characters. Hence $h$ only decreases by 1 per step but can be re-grown by scanning forward — total growth is bounded by $n$ , total shrink by $n$ → $O(n)$ amortized.

Worked example LCP for "banana",

$SA=[5,3,1,0,4,2]$ rank $=[3,2,5,1,4,0]$ (inverse). Walk by $i$ :

i=0 rank3 pred=SA[2]=1: suf0=banana, suf1=anana → LCP 0. h=0→ h=0
i=1 rank2 pred=SA[1]=3: anana vs ana → match "ana"=3. LCP[2]=3. h=3-1=2
i=2 rank5 pred=SA[4]=4: nana vs na → "na"=2. LCP[5]=2. h=1
i=3 rank1 pred=SA[0]=5: ana vs a → "a"=1. LCP[1]=1. h=0
i=4 rank4 pred=SA[3]=0: na vs banana → 0. LCP[4]=0. h=0
i=5 rank0: no pred. h=0

Result indexed by sorted rank: $\text{LCP}=[0,1,3,0,0,2]$ . Why the +1 reuse at i=1→i=2? After matching "ana" (h=3) we drop to 2 and the next suffix indeed starts with at least that overlap — saving a re-scan.

4. Common mistakes (Steel-man → fix)

Recall Feynman: explain to a 12-year-old

Imagine you cut a word like "banana" into all its tails: "banana", "anana", "nana", "ana", "na", "a". Now put these tails in dictionary order like words in a dictionary. The suffix array is just the page numbers (starting positions) in that sorted list. To sort them fast we're lazy: first we only compare the first letter, then first two letters, then four, doubling each time — because to know the first 4 letters of a tail we glue together two "first 2 letters" answers we already computed. The LCP numbers tell you how many starting letters two neighboring tails share — handy for spotting repeats.

Connections

Suffix Tree — same problems, more memory; SA is its flattened cousin.
Radix Sort / Counting Sort — the per-round linear sort enabling $O(n\log n)$ .
Binary Search on Suffix Array — pattern matching in $O(m\log n)$ .
Sparse Table / RMQ — combine with LCP for $O(1)$ LCP of any two suffixes.
Z-Algorithm / KMP — alternative substring tools (single pattern).
Burrows–Wheeler Transform — built directly from the suffix array.

Flashcards

What is the suffix array of a string?

The array of starting indices of all suffixes, sorted lexicographically.

What is the rank array and how does it relate to SA?

rank is the inverse permutation: rank[SA[r]] = r; it gives each suffix's sorted position.

Core idea of

O(n\log n)

suffix array construction?

Prefix-doubling: sort by first k chars using rank pairs (rank_k[i], rank_k[i+k]), doubling k each round.

Why is the comparison key for the next round a pair of previous ranks?

First 2k chars of suffix i = (first k of suf i)+(first k of suf i+k), whose orders are already known ranks.

How many doubling rounds and total complexity (with radix sort)?

⌈log₂ n⌉ rounds × O(n) each = O(n log n).

What sentinel for rank_k[i+k] when i+k ≥ n, and why?

−1 (smaller than any real rank), because a shorter suffix must sort before a longer one sharing its prefix.

What does LCP[r] measure?

Length of longest common prefix of the two adjacent sorted suffixes suf(SA[r−1]) and suf(SA[r]).

Key lemma behind Kasai's O(n) LCP algorithm?

When moving from suffix i to i+1, the LCP with its predecessor drops by at most 1.

Why does Kasai carry h over instead of resetting to 0?

To keep amortized O(n); resetting causes O(n²) re-scanning.

Formula for number of distinct substrings via SA and LCP?

Σ(n − SA[r]) − Σ LCP[r].

Common mistake about which suffixes LCP compares?

It compares neighbors in sorted (SA) order, not suffixes at index r and r+1.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Suffix array ka matlab simple hai: ek string ke saare suffixes (tails) ko dictionary order mein sort karke unke starting index store kar lo. Jaise "banana" ke suffixes ko sort karo to milta hai a, ana, anana, banana, na, nana — aur unke indices ka array $SA=[5,3,1,0,4,2]$ ban jaata hai. Faayda ye ki kisi bhi pattern ko dhoondhna ho to woh sorted suffixes mein ek contiguous block banata hai, jise binary search se pakad lo.

Construction ka asli jugaad hai prefix-doubling. Pure suffix compare karna mehenga ( $O(n^2\log n)$ ). Isliye hum lazy hote hain: pehle sirf 1 letter se sort, phir 2 letters, phir 4, doubling karte jao. Trick ye hai ki kisi suffix ke first $2k$ letters ka order = (uske first $k$ ka rank, aur $k$ aage wale suffix ke first $k$ ka rank) — yaani ek pair $(r_k[i], r_k[i+k])$ . Ye pairs already pata hote hain, to bas pairs ko sort karo. $\log n$ rounds, har round $O(n)$ radix sort se → total $O(n\log n)$ . Ek dhyaan: jab $i+k$ string se bahar jaaye to rank $-1$ (sabse chhota) lo, kyunki chhota suffix pehle aata hai.

LCP array batata hai ki sorted order mein bagal-bagal wale do suffixes kitne shuru ke letters share karte hain. Iska linear-time algorithm Kasai ka hai, jiska core lemma: jab suffix $i$ se $i+1$ pe jaate ho, LCP zyada se zyada 1 hi girta hai. Isliye $h$ ko reset mat karo, bas $h-1$ se shuru karke aage match karo — amortized $O(n)$ . Iska use? Distinct substrings ginna ( $\sum(n-SA[r]) - \sum LCP[r]$ ), longest repeated substring (max LCP), waghairah. Yaad rakho: LCP sorted neighbours ka hai, index $r$ aur $r+1$ ka nahi — yahi sabse common galti hai.

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

1. Definitions

2. Construction in $O(n\log n)$ — derived from scratch

3. The LCP array — Kasai's $O(n)$ algorithm, derived

4. Common mistakes (Steel-man → fix)

Connections

Flashcards

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — String Algorithms

Connections