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

Put the four tails in dictionary order. Compare letter by letter:

• $\text{ab}$ (from index 2) vs $\text{abab}$ (index 0): they agree on ab, then abab continues while ab ends. A string that ends is smaller (shorter prefix wins). So $\text{ab}<\text{abab}$.
• Both a-starting tails come before both b-starting tails.
• Among b: $\text{b}$ (index 3) vs $\text{bab}$ (index 1): b ends first → smaller. So $\text{b}<\text{bab}$.

Sorted: $\text{ab}(2)<\text{abab}(0)<\text{b}(3)<\text{bab}(1)$. $SA=[2,0,3,1]$

$\text{rank}$ is the inverse permutation: $\text{rank}[SA[r]]=r$. Walk $r=\mathrm{0..3}$:

• $SA[0]=2\Rightarrow \text{rank}[2]=0$
• $SA[1]=0\Rightarrow \text{rank}[0]=1$
• $SA[2]=3\Rightarrow \text{rank}[3]=2$
• $SA[3]=1\Rightarrow \text{rank}[1]=3$

$\text{rank}=[1,3,0,2]$

Glue "first-2-letters" from two "first-1-letter" answers. Off the end $\to -1$:

i=0: (r1[0], r1[2]) = (0, 0)
i=1: (r1[1], r1[3]) = (1, 1)
i=2: (r1[2], -1)    = (0, -1)
i=3: (r1[3], -1)    = (1, -1)

Sort pairs ascending (compare first component, then second): $(0,-1)\to i=2$, $(0,0)\to i=0$, $(1,-1)\to i=3$, $(1,1)\to i=1$. $SA=[2,0,3,1]$ Matches L1.1 exactly — two characters already fully separated these suffixes, so this round is final. (Uses Radix Sort / Counting Sort on the pair components for $O(n)$ per round.)

Walk by starting index $i$, predecessor $j=SA[\text{rank}[i]-1]$, extend $h$ while $s[i+h]=s[j+h]$, then $h\leftarrow \max (h-1,0)$:

i=0 rank=1 pred=SA[0]=2: suf0=abab vs suf2=ab -> match "ab"=2. LCP[1]=2. h=1
i=1 rank=3 pred=SA[2]=3: suf1=bab  vs suf3=b  -> match "b" =1. LCP[3]=1. h=0
i=2 rank=0 : no predecessor -> h=0
i=3 rank=2 pred=SA[1]=0: suf3=b    vs suf0=abab -> match ""=0. LCP[2]=0. h=0

Store by sorted position, $\text{LCP}[0]=0$ by convention: $\text{LCP}=[0,2,0,1]$ Reading it: neighbors $SA[0]=2,SA[1]=0$ (ab,abab) share 2; $SA[1]=0,SA[2]=3$ (abab,b) share 0; $SA[2]=3,SA[3]=1$ (b,bab) share 1. ✅

• Total prefixes over all suffixes: $\sum (n-SA[r])=(4-2)+(4-0)+(4-3)+(4-1)=2+4+1+3=10$.
• Overlaps double-counted: ${\sum }_{r\ge 1}\text{LCP}[r]=2+0+1=3$.
• Distinct $=10-3=7$.

Sanity list: length-1 a,b; length-2 ab,ba; length-3 aba,bab; length-4 abab. That is $2+2+2+1=7$. ✅

Suffix $i$ has run out of characters — its true tail is shorter. A shorter string that is a prefix of the other must come first in dictionary order. The rule sets $r_k[i+k]=-1$ and keeps $r_k[j+k]=0$. Since $-1<0$, the pair $(\cdot ,-1)$ sorts before $(\cdot ,0)$, placing suffix $i$ first. ✅ Correct. If we had used $0$ (or garbage) for the off-end, the tie would break arbitrarily and could place the longer suffix first — a bug. The sentinel encodes "end-of-string is smaller than any letter".

$k$ runs $1,2,4,8,\dots$. We stop when $k\ge 1000$: $2^9=512<1000\le 1024=2^{10}$. So we need $k=1024$, reached after 10 doublings from $k=1$ ($1\to 2\to 4\to 8\to 16\to 32\to 64\to 128\to 256\to 512\to 1024$). This is $\lceil {\log }_{2}n\rceil =\lceil {\log }_{2}1000\rceil =10$. Each round is $O(n)$ with radix sort → total $O(n\log n)$.

$\max \text{LCP}=3$ at $r=2$. So the longest repeated substring has length $3$, starting at $SA[2]=1$: $s[\mathrm{1..3}]=\text{"ana"}.$ Check: ana occurs at index 1 (b**ana**na) and index 3 (ban**ana**). ✅ Why LCP finds it: a repeated substring is a common prefix of two different suffixes; the largest such common prefix among all pairs is achieved by some adjacent pair in sorted order (sorting clusters similar tails together), which is precisely what the LCP array records. See figure.

Because $SA$ lists tails in dictionary order, every tail beginning with na sits together. The sorted tails are:

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

Tails whose prefix is na: rows $r=4$ (na) and $r=5$ (nana). Block $=[4,5]$, so na occurs 2 times, at positions $SA[4]=4$ and $SA[2\text{’s row}]=2$, i.e. indices $\{4,2\}$. Two binary searches (lower + upper bound) find this block in $O(|p|\log n)$.

$\text{rank}[1]=2$, $\text{rank}[3]=1$. Order them: smaller rank $=1$ (suffix 3), larger $=2$ (suffix 1). Range is $r\in \{2\}$ (i.e. $r$ from $1+1$ to $2$): $\min \{\text{LCP}[2]\}=\min \{3\}=3$. Direct check: $\text{suf}(1)=\text{anana}$, $\text{suf}(3)=\text{ana}$ share ana (length 3). ✅ Why the min: walking from rank $a$ down to rank $b$ in sorted order, the shared prefix can only shrink or stay — each adjacent step removes at most the difference recorded in $\text{LCP}$. The tightest bottleneck is the minimum. That min-over-a-range query is answered in $O(1)$ by a sparse table after $O(n\log n)$ preprocessing.

For $s=\text{"aa"}$: tails aa(0), a(1). Sorted: a(1) < aa(0), so $SA=[1,0]$. $\text{LCP}[1]=$ LCP(a,aa)$=1$. Distinct $=\sum (n-SA[r])-\sum \text{LCP}=[(2-1)+(2-0)]-1=(1+2)-1=2$. Check: distinct substrings of aa are a,aa → 2. ✅ For $s=\text{"aaa"}$: $SA=[2,1,0]$ (a<aa<aaa), $\text{LCP}=[0,1,2]$. Distinct $=[(3-2)+(3-1)+(3-0)]-(1+2)=(1+2+3)-3=6-3=3$. Check: a,aa,aaa → 3. ✅ Insight: appending one repeated character adds exactly one new distinct substring here (the full new run), because every shorter run already existed. A string of $m$ identical letters has exactly $m$ distinct substrings.

Let $\text{suf}(i)$ have predecessor $\text{suf}(j)$ in sorted order sharing $h\ge 1$ characters. Since $s[i]=s[j]$, dropping the first char gives $\text{suf}(i+1)$ and $\text{suf}(j+1)$ sharing $h-1$ characters, and crucially $\text{suf}(j+1)$ still sorts before $\text{suf}(i+1)$ (removing an equal leading char preserves order). The true predecessor of $\text{suf}(i+1)$ is at least as close as $\text{suf}(j+1)$, so it shares at least $h-1$ chars. Hence starting the scan at $h-1$ never overshoots. Cost bound: $h$ increases by the number of while-loop character matches and decreases by at most $1$ per step. Over all $n$ steps total decrease $\le n$, so total increase $\le n+h_{\text{final}}\le 2n$. Therefore the combined match work is $O(n)$ — linear. ∎

L1 ::: Read $SA$ (sorted tail indices) and invert it to $\text{rank}$; string-end is smallest. L2 ::: One doubling round glues rank-pairs; Kasai walks by index carrying $h$. L3 ::: Distinct $=\sum (n-SA[r])-\sum \text{LCP}$; the $-1$ sentinel forces shorter suffixes first. L4 ::: $\max \text{LCP}$ = longest repeated substring; pattern hits form a contiguous $SA$ block. L5 ::: LCP of any pair = range-min of $\text{LCP}$; Kasai is $O(n)$ by the drop-by-one lemma.