WHAT. Take a string. A suffix is just a tail of that string: pick a starting position and read to the very end.
WHY. Every substring you could ever search for is the front part of some tail. So if we understand tails, we understand all substrings. That is the whole reason this data structure exists.
PICTURE. Below, the word banana is written once, and each colored bracket marks where one tail begins and runs to the end. The number under each bracket is its starting indexi (we count from 0).
WHAT. We are going to sort these tails the way a dictionary sorts words: compare the first letter; if tied, compare the second; and so on. That rule is called lexicographic order.
WHY. In a dictionary, all words starting the same way sit together in one block. Same here: after sorting, every tail beginning with the same letters forms a contiguous run. That contiguity is what later lets binary search find any pattern.
PICTURE. Two tails are compared column by column. The first column where they differ decides the winner — and a shorter tail that has run out of letters is treated as smaller (the string "ended", and end-of-string is the smallest thing there is).
WHAT. Sorting the tails by comparing whole strings works, but each comparison can scan up to n letters, and there are n tails — that is painfully slow. Instead we sort using only the first k letters of every tail, and we will grow k.
WHY. If we only look at the first k letters, tails that agree on those k letters tie. We record ties with a rank: equal keys get the same rank number. Later, growing k breaks the ties. This "look at a little, then a little more" is the seed of the fast method.
PICTURE. For k=1 we only see the first letter. All three tails starting with a tie (rank 0); b gets rank 1; both n tails tie (rank 2).
WHAT. We already have ranks for the first k letters (call them rk). To sort by the first 2k letters, we do not re-read 2k letters. We build a pair key for each tail:
key2k(i)=(rk[i],rk[i+k])
WHY. The first 2k letters of suf(i) split into two blocks of length k: the block starting at i, and the block starting at i+k. But "the first k letters starting at i+k" is exactly the front of suf(i+k), which rk[i+k] already ranks! So the first half is summarized by rk[i] and the second half by rk[i+k]. Comparing the pair compares the first 2k letters — using numbers we already have. This is why the method is called prefix doubling.
PICTURE. The arrow shows how the second half of a tail is itself the front of a shorter tail we already ranked. That reuse is the whole magic.
WHAT. When i+k≥n, the second block "starts past the end of the string" — there are no letters there. We assign that half the special value −1.
WHY. A tail that has ended must sort before any tail that still has letters (recall Step 2: end-of-string is smallest). If we lazily plugged in 0 or garbage, a short tail like a could wrongly sort after a longer tail like ana even though a must come first. Using −1, a value smaller than every real rank (0,1,2,…), forces the ended tail to the front.
PICTURE. Two tails that agree on their first k letters: one still has more letters, the other has run out. The −1 tag pushes the ended one earlier.
Now run the first doubling round on banana: k=1, so the offset is i+1 and we form key2(i)=(r1[i],r1[i+1]). With r1=[1,0,2,0,2,0]:
i=0:(1,0) & i=1:(0,2) & i=2:(2,0) &\\
i=3:(0,2) & i=4:(2,0) & i=5:(0,-1) &
\end{array}$$
Term by term: $\text{key}_2(0)=(r_1[0],r_1[1])=(1,0)$ from `ba`; $\text{key}_2(5)=(r_1[5],-1)=(0,-1)$ because `a` runs off the end.
**Sorting the pairs ascending** gives the index order $5,3,1,0,4,2$:
$$5\!:\!(0,\text{-}1)\;<\;3\!:\!(0,2)=1\!:\!(0,2)\;<\;0\!:\!(1,0)\;<\;4\!:\!(2,0)=2\!:\!(2,0)$$
**How we read off the new ranks $r_2$ from this sorted list** — scan the sorted pairs left to right, starting a counter at $0$; **give equal keys the same rank, and bump the counter by $1$ only when the key changes**:
| position | index | key | key changed? | rank $r_2$ |
|---|---|---|---|---|
| 0 | 5 | $(0,-1)$ | start | $0$ |
| 1 | 3 | $(0,2)$ | yes | $1$ |
| 2 | 1 | $(0,2)$ | no (tie with 3) | $1$ |
| 3 | 0 | $(1,0)$ | yes | $2$ |
| 4 | 4 | $(2,0)$ | yes | $3$ |
| 5 | 2 | $(2,0)$ | no (tie with 4) | $3$ |
Writing $r_2$ back **by starting index** (not by sorted position): $r_2=[2,1,3,1,3,0]$. Notice indices $1$ and $3$ still tie (both `an…`), and $2$ and $4$ still tie (both `na…`) — two chars is not yet enough. One more round ($k=2$, offset $i+2$) breaks these ties and finishes the sort.
---
## Step 6 — After $\log n$ rounds we are done: the finished suffix array
**WHAT.** Each round **doubles** $k$: $1 \to 2 \to 4 \to \dots$. Once $k \ge n$, no two distinct tails can still be tied, so the ranks are the true final order. The number of rounds is $\lceil \log_2 n \rceil$.
**WHY the cost is $O(n\log n)$.** There are $\lceil\log_2 n\rceil$ rounds. Each round must sort $n$ pairs whose entries are integers in $[-1, n)$. A naive comparison sort costs $O(n\log n)$ per round → $O(n\log^2 n)$ total (simpler to code, fine in contests). To hit the true $O(n\log n)$ we sort each round in $O(n)$ using a **two-pass [[Radix Sort|radix sort]]** built from [[Counting Sort|counting sort]]:
> [!intuition] Why two passes and why *stable* sorting is essential
> A pair key has two coordinates $(a,b)=(r_k[i],\,r_k[i+k])$. Radix sort sorts by the **least-significant coordinate first**: pass 1 sorts all indices by $b$ (the second half), pass 2 sorts by $a$ (the first half). For the final order to be correct, pass 2 must **not disturb** the order that pass 1 established among equal $a$'s — that property is called ==stability==. [[Counting Sort]] is stable if you place equal keys in first-seen order, so ties on $a$ keep their pass-1 ordering by $b$. Each pass touches $n$ items with keys in $[0,n)$, so each pass is $O(n)$ and the round is $O(n)$.
Multiply $O(n)$ per round by $\lceil\log_2 n\rceil$ rounds → $O(n\log n)$.
**PICTURE.** The final sorted list of tails, with the array $SA$ = their starting indices read top to bottom.
![[deepdives/dd-coding-3.8.07-d2-s06.png]]
> [!definition] Suffix array $SA$ and rank array
> $$SA = [\,5,\ 3,\ 1,\ 0,\ 4,\ 2\,]$$
> - $SA[r]$ ::: starting index of the $r$-th smallest tail
> - $\text{rank}[i]$ ::: where tail $i$ landed in sorted order — the *inverse* of $SA$
> Here $\text{rank} = [3,2,5,1,4,0]$, meaning $\text{rank}[SA[r]] = r$ for every $r$.
---
## Step 7 — Measuring neighbors: the LCP array
**WHAT.** Now that tails are sorted, ask: how many starting letters does each tail share with the tail **just above it** in the sorted list? That count is the **LCP** (Longest Common Prefix) of *adjacent-in-sorted-order* tails.
**WHY.** Neighbors in the sorted list are the *most similar* tails possible. Their shared prefix length reveals repeats in the string and, summed up, counts distinct substrings. Comparing only neighbors (not all pairs) is enough because a shared prefix of any two tails is bounded by the LCPs along the run between them.
**PICTURE.** The sorted list again, now with a bracket between each pair of neighbors showing how many leading letters match.
![[deepdives/dd-coding-3.8.07-d2-s07.png]]
> [!definition] LCP array
> $\text{LCP}[r]$ = number of leading letters shared by $\text{suf}(SA[r-1])$ and $\text{suf}(SA[r])$, for $r = 1,\dots,n-1$; and $\text{LCP}[0]=0$.
> For `banana`: $\text{LCP} = [\,0,\ 1,\ 3,\ 0,\ 0,\ 2\,]$.
> - $\text{LCP}[2]=3$ ::: `ana` and `anana` share `ana`
> - $\text{LCP}[5]=2$ ::: `na` and `nana` share `na`
> [!mistake] "LCP[r] compares suffix index $r$ with index $r+1$."
> *Feels right:* they look adjacent. *Truth:* adjacency is in **sorted order**, i.e. $SA[r-1]$ vs $SA[r]$ — not raw indices. **Fix:** always say "neighbors in the array."
---
## Step 8 — Kasai's linear-time LCP: the "drops by at most 1" lemma
**WHAT.** Instead of recomputing each LCP from scratch, walk the tails in order of **starting index** $i=0,1,2,\dots,n-1$ and carry a **single running match length** $h$ that we *initialize once* to $0$ and never reset by hand.
**WHY (the lemma).** Suppose $\text{suf}(i)$ shares $h$ letters with its sorted predecessor. Chop off the first (shared) letter of both: we get $\text{suf}(i+1)$ and a tail that still shares $h-1$ letters with it *and* still sits earlier in sorted order. So the true predecessor of $\text{suf}(i+1)$ shares **at least** $h-1$ letters. Hence $h$ can fall by at most $1$ per step. It rises only by scanning forward, and total forward scanning across all steps is bounded by $n$ → **$O(n)$ overall**.
**PICTURE.** Left: matched $h$ letters for tail $i$. Right: strip one letter, and the guaranteed $h-1$ overlap survives for tail $i+1$ — no need to re-scan those letters.
![[deepdives/dd-coding-3.8.07-d2-s08.png]]
> [!formula] Kasai's algorithm — the exact loop
> ```
> h = 0 # ONE variable, initialized once
> for i in 0, 1, 2, ..., n-1: # walk by starting index
> if rank[i] == 0: # suf(i) is the smallest -> no predecessor
> h = 0 # nothing above it to compare; leave h = 0
> continue
> j = SA[rank[i] - 1] # predecessor's starting index
> while i+h < n and j+h < n and s[i+h] == s[j+h]:
> h = h + 1 # extend the match one letter at a time
> LCP[rank[i]] = h # record it
> h = max(h - 1, 0) # carry the guaranteed overlap forward
> ```
> - $h$ ::: initialized to $0$ **once** before the loop; the whole method rests on *not* resetting it
> - `rank[i] == 0` case ::: there is genuinely no neighbor above, so the LCP is undefined/`0`; setting $h=0$ here is **not** the forbidden reset — there is simply nothing to carry, because a smallest suffix has no predecessor to share letters with
> - `while` guards ::: `i+h<n` and `j+h<n` stop us reading past either tail's end
> - $h=\max(h-1,0)$ ::: the *only* decrement, applied after recording — this is what keeps the total work $O(n)$
> [!mistake] Resetting $h=0$ on **every** iteration.
> *Feels right:* fresh tail, fresh count. *Cost:* you throw away the guaranteed overlap and re-scan everything → $O(n^2)$. **Fix:** declare $h$ *outside* the loop, initialize it to $0$ once, and only ever change it via `h += 1` (extend) or `h = max(h-1, 0)` (carry). The single exception is the "no predecessor" branch (`rank[i]==0`), where there is nothing above to compare — that is a genuine absence of overlap, not a reset of hard-won progress.
> [!example] Kasai on "banana", $SA=[5,3,1,0,4,2]$, $\text{rank}=[3,2,5,1,4,0]$
> ```
> h=0 start
> i=0 rank3 pred=SA[2]=1: banana vs anana -> 0 match. LCP[3]=0. h=max(-1,0)=0
> i=1 rank2 pred=SA[1]=3: anana vs ana -> "ana"=3. LCP[2]=3. h=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 predecessor -> h=0, continue
> ```
> Result indexed by sorted rank: $\text{LCP}=[0,1,3,0,0,2]$. The $h=2$ carried into $i=2$ (instead of rescanning from $0$) is exactly the amortization the lemma promised.
---
## Step 9 — Payoff: counting distinct substrings with the LCP array
**WHAT.** Every substring of $s$ is the front of exactly one tail. If we list, for each sorted tail, all of its prefixes, we count every substring — but with duplicates. The LCP tells us exactly how many prefixes a tail shares with its predecessor, so we subtract those.
**WHY.** Tail $SA[r]$ offers $n - SA[r]$ prefixes. Of those, the first $\text{LCP}[r]$ already appeared in the previous tail (that is what "shared prefix" means). Subtract the overlaps to count each distinct substring once.
**PICTURE.** A staircase: each tail's prefixes stacked, with the LCP-shared portion shaded as "already counted".
> [!formula] Distinct-substring count
> $$\#\text{distinct} = \sum_{r=0}^{n-1}\big(n - SA[r]\big)\; -\; \sum_{r=1}^{n-1}\text{LCP}[r]$$
> - $n - SA[r]$ ::: number of prefixes (substrings) that tail $SA[r]$ contributes
> - $\sum \text{LCP}[r]$ ::: total prefixes already counted by a predecessor
>
> For `banana`: $\sum(n-SA[r]) = 1+3+5+6+2+4 = 21$ and $\sum\text{LCP} = 0+1+3+0+0+2 = 6$, so $\#\text{distinct} = 21 - 6 = 15$.
---
## The one-picture summary
The entire pipeline on one page: cut into tails → sort by doubling with pair keys and the $-1$ sentinel → read off $SA$ → measure neighbor overlaps with Kasai to get LCP → harvest results.
> [!recall]- Feynman retelling — the whole walk in plain words
> Chop `banana` into all its tails and imagine putting them in dictionary order. To sort fast we're lazy: first compare just one letter (lots of ties), then two, then four, doubling each time. The trick that makes doubling cheap is that the *next $k$ letters* of a tail are the *first $k$ letters* of a shorter tail we already ranked — so we compare **pairs of rank numbers** instead of re-reading letters, and the offset we look ahead by is exactly the current $k$ (1, then 2, then 4…). Tails that hit the end of the string get a $-1$ tag so they float to the front, exactly like the shortest word wins in a dictionary. To turn a round's sorted pairs back into ranks we scan them once, giving equal pairs the same number and only bumping when the pair changes. Because the keys are small integers we can sort each round with a *stable* two-pass counting/radix sort in linear time, so the whole build is $n\log n$. Then we measure how many starting letters each tail shares with the one above it — that's the LCP array — and Kasai's trick says that count can only drop by one each time we shift to the next start position (using one carried variable $h$), so measuring all of them is linear work. From those overlap numbers we can instantly count that `banana` has 15 distinct substrings.
> [!recall]- Self-test
> What is the key you sort by in round $2k$? ::: The pair $(r_k[i],\ r_k[i+k])$ — ranks of the two length-$k$ halves; the offset $k$ starts at $1$ and doubles each round.
> How do you turn the sorted pairs back into the new rank array? ::: Scan left to right, start a counter at $0$, give equal keys the same rank, and increment only when the key changes; write the rank back by starting index.
> Why must the per-round sort be stable? ::: Radix sorts by the 2nd coordinate then the 1st; stability keeps the 2nd-coordinate order among ties on the 1st, so the pair order stays correct — and keeps each pass $O(n)$.
> Why $-1$ when $i+k\ge n$? ::: The tail ended; end-of-string is smallest, so it must sort first.
> Why is Kasai $O(n)$? ::: One carried variable $h$ drops by at most $1$ per step, so total scanning is bounded by $n$.
> Distinct substrings of `banana`? ::: $21 - 6 = 15$.
Related maps: [[Suffix Tree]], [[Sparse Table / RMQ]] (for $O(1)$ LCP queries), [[Z-Algorithm]], [[KMP]], [[Burrows–Wheeler Transform]].
