Suffix Trees and Suffix Arrays

A suffix of a string $S$ of length $n$ is the substring $S[i \ldots n-1]$ starting at position $i$, for $i = 0, \dots, n-1$. There are exactly $n$ suffixes, one per starting index, including the full string itself ($i=0$) and the single last character ($i = n-1$). The suffix array $SA$ of $S$ is a permutation of $\{0, \dots, n-1\}$ listing suffix start positions in lexicographically increasing order of the suffixes they name. To make comparisons total and well-defined, we append a unique sentinel character `$`, smaller than every character in the alphabet, guaranteeing no suffix is a prefix of another and that comparisons always terminate. The key insight is that any substring of$S$is a prefix of exactly one suffix. Consequently, all occurrences of a query pattern$P$correspond exactly to the suffixes of$S$that begin with$P$— and because$SA$is sorted, those suffixes occupy a contiguous range. Finding all occurrences of$P$reduces to finding the range of the sorted suffix list whose entries start with$P$, which is a textbook binary search: two binary searches locate the lower and upper bound of that range in$O(m \log n)$time, where$m = |P|$. The **LCP array** complements$SA$:$\mathrm{LCP}[i]$is the length of the longest common prefix shared by the suffixes at$SA[i-1]$and$SA[i]$(with$\mathrm{LCP}[0]$undefined or set to$0$by convention). Because sorted order groups similar suffixes together, the LCP array reveals shared structure directly: the longest repeated substring in$S$is the maximum value in the LCP array, and the number of *distinct* substrings of$S$equals$\binom{n}{2}$-style sums of prefix lengths minus overlaps — precisely$\sum_i (n - SA[i]) - \mathrm{LCP}[i]$. Together$SA$and$LCP$are functionally equivalent to a **suffix tree**: a compressed trie whose leaves are the$n$suffixes in left-to-right sorted order, whose internal branching nodes correspond exactly to LCP local minima, and whose edge-label concatenations from root to leaf$i$spell out suffix$SA[i]$. This equivalence is the conceptual bridge: a suffix array is a suffix tree with the tree structure flattened into two arrays, at large memory savings.

We build the structure in two stages: first sort the suffixes to get $SA$, then derive $LCP$ from $SA$.

Naive construction. Sorting all $n$ suffixes directly with a general comparison sort costs $O(n \log n)$ comparisons, but each comparison between two suffixes can itself take $O(n)$ time in the worst case (e.g., text `aaaa...a`), giving $O(n^2 \log n)$ overall — too slow for texts beyond a few thousand characters.

Manber–Myers prefix doubling. The efficient approach sorts suffixes not by their full content at once, but by progressively longer prefixes, doubling the compared length each round: first by 1-character prefixes, then by 2-character prefixes (reusing the 1-character ranks), then 4, then 8, and so on, until the compared prefix length exceeds $n$. After $\lceil \log_2 n \rceil$ rounds, all ties are broken and the ranks give the exact sorted order. The trick that makes each round fast: a suffix's rank by $2k$-character prefix is determined by the pair (rank-by-$k$-prefix of itself, rank-by-$k$-prefix of the suffix $k$ positions later). Sorting these $O(n)$ pairs by radix sort (or a comparison sort) takes $O(n \log n)$ or $O(n)$ per round; with $O(\log n)$ rounds the total is $O(n \log^2 n)$ with comparison sorting, or $O(n \log n)$ with radix sorting of the pairs — the latter is the standard bound quoted for this algorithm. ``` function BUILD-SUFFIX-ARRAY(S): n = length(S) append sentinel '$' to S # smaller than all characters n = n + 1

# round 0: rank by single character rank = array of size n for i in 0..n-1: rank[i] = ORD(S[i]) SA = [0, 1, ..., n-1] k = 1 while k < n:

# comparator: compare (rank[i], rank[i+k] or -1) pairs define key(i): first = rank[i] second = rank[i + k] if i + k < n else -1 return (first, second) sort SA by key(·) # O(n log n) comparison sort

# (or O(n) via radix sort on pairs)

# recompute ranks: equal keys get equal rank newRank = array of size n newRank[SA[0]] = 0 for idx in 1..n-1: prevSuffix = SA[idx - 1] currSuffix = SA[idx] if key(currSuffix) == key(prevSuffix): newRank[currSuffix] = newRank[prevSuffix] else: newRank[currSuffix] = newRank[prevSuffix] + 1 rank = newRank if rank[SA[n-1]] == n - 1: break # all suffixes fully distinguished k = k 2 return SA ``` Once $SA$ is built, <strong>Kasai&#39;s algorithm</strong> computes $LCP$ in linear time by exploiting a monotonicity property: if suffix $S[i \ldots]$ has LCP value $h$ with its predecessor in sorted order, then suffix $S[i+1 \ldots]$ (the suffix obtained by chopping one character off the front) has LCP at least $h - 1$ with its predecessor in sorted order. This lets us walk through the text in original index order (not sorted order), maintaining a running match-length counter that only ever decreases by 1 per step, so its total* decrease across the whole pass is bounded by $n$ even though it may increase arbitrarily at each step. ``` function BUILD-LCP-ARRAY(S, SA): n = length(S) rankOfSuffix = array of size n # inverse permutation of SA for i in 0..n-1: rankOfSuffix[SA[i]] = i LCP = array of size n, all zero h = 0 for i in 0..n-1: if rankOfSuffix[i] > 0: j = SA[rankOfSuffix[i] - 1] # predecessor suffix in sorted order while i + h < n and j + h < n and S[i + h] == S[j + h]: h = h + 1 LCP[rankOfSuffix[i]] = h if h > 0: h = h - 1 else: h = 0 return LCP ``` Substring search against the finished structure uses two binary searches over $SA$, comparing the query pattern $P$ character by character against the suffix starting at each candidate position: ``` function SEARCH-RANGE(S, SA, P): lo = LOWER-BOUND(S, SA, P) # first index with suffix >= P lexicographically hi = UPPER-BOUND(S, SA, P) # first index with suffix > (P followed by max char) if lo == hi: return "not found" return SA[lo .. hi - 1] # all starting positions of occurrences of P ``` Each comparison in the binary search costs up to $O(m)$ character comparisons, so the whole search costs $O(m \log n)$. With additional preprocessing (the LCP array combined with the range-minimum-query technique), this bound improves to $O(m + \log n)$, matching suffix-tree query time.

Suffix array construction. The Manber–Myers doubling scheme runs $O(\log n)$ rounds (since the compared prefix length doubles from 1 to at least $n$). Each round performs a sort of $n$ rank-pairs. Using a comparison sort this costs $O(n \log n)$ per round, giving an overall $O(n \log^2 n)$; using radix sort on the bounded-range pair keys, each round drops to $O(n)$, giving the commonly quoted $O(n \log n)$ total. (Truly linear-time suffix array construction algorithms — DC3/skew, SA-IS — exist and run in $O(n)$, but they are substantially more intricate; the doubling algorithm is the standard teaching and practical choice, and is what production libraries often ship for moderate-size texts.) Correctness of doubling follows by induction on the round index $r$, where the invariant is: after round $r$ (comparing $k = 2^r$-character prefixes), suffixes are correctly grouped and ordered by their first $k$ characters, with equal-key suffixes tied at equal rank. The base case $r=0$ holds trivially by definition of the initial rank array (single characters). For the inductive step, two suffixes' first $2k$ characters are compared exactly by the pair (first $k$ characters of self, first $k$ characters of the suffix shifted right by $k$) — this pair is the rank pair used as sort key, and by the inductive hypothesis the ranks used already correctly order $k$-character prefixes. So sorting by these pairs correctly orders $2k$-character prefixes. The loop terminates once $k \geq n$, because with $n$ distinct suffixes over a text of length $n$ (plus sentinel), a prefix length of $n$ characters uniquely distinguishes every suffix — the sentinel guarantees no suffix is a proper prefix of another, so no ties can survive that long.

LCP construction (Kasai). The algorithm runs in $O(n)$ time. The correctness argument rests on one lemma: if $\mathrm{LCP}(S_i, S_{i-1\text{'s predecessor}}) = h$ (in rank terms), then when we move to suffix $S_{i+1}$ (one character shorter), its LCP with its rank-predecessor is at least $h - 1$. This holds because removing the first character from both $S_i$ and its predecessor $S_j$ (which shared $h$ characters, $h \geq 1$) yields $S_{i+1}$ and $S_{j+1}$, which still share the last $h-1$ of those characters; and since suffix order is compatible with this shift (a known lexicographic fact: if $S_j < S_i$ and both start with the same character, then $S_{j+1}$ and $S_{i+1}$ remain correctly ordered relative to some suffix no worse in rank distance), the actual predecessor of $S_{i+1}$ in the array shares at least those $h-1$ characters. So the match-length variable `h` in the pseudocode never needs to restart from 0; it only decreases by at most 1 per outer-loop iteration, while the inner `while` loop can only increase `h`. Summing increases and decreases: total decreases across the whole run are at most $n$ (h decreases by at most 1, $n$ times), so total increases (the work done in all inner-loop iterations combined) are also bounded by $O(n)$ — this is a standard amortized analysis via a potential function equal to the current value of `h`.

Substring search. Binary search over $n$ sorted suffixes takes $O(\log n)$ comparisons; each suffix-vs-pattern comparison costs up to $O(m)$ character operations in the worst case, giving $O(m \log n)$ total — honest and simple, though not optimal. Precomputing, for each binary-search step, the LCP information between the query and known boundary suffixes (a technique using the LCP array plus a sparse table for range-minimum queries) removes redundant character comparisons and achieves $O(m + \log n)$.

Suffix tree comparison. A suffix tree, built via Ukkonen's algorithm, achieves $O(n)$ construction time and $O(m)$ pattern search time (no logarithmic factor) — asymptotically better for search — but at the cost of substantially higher constant-factor memory: each internal node needs child pointers (often via a hash map or fixed-size array over the alphabet), suffix links, and edge-label ranges, typically costing 10–20 bytes per character of text versus roughly 4–8 bytes per character for a suffix array plus LCP array packed as integer arrays. In memory-constrained settings — indexing a multi-gigabase genome, for instance — the suffix array's compactness often outweighs its extra $\log n$ query factor, which is why practical bioinformatics tools (e.g., BWA, based on the closely related FM-index/Burrows–Wheeler transform) favor array-based structures.

Honest tradeoffs. The suffix array is not asymptotically optimal for single-pattern search compared to a suffix tree, and building it in true linear time requires the more complex DC3/SA-IS family of algorithms rather than the doubling method shown here. The doubling method's $O(n \log n)$ bound (with radix sort) is a solid, teachable, and practically fast compromise — but if $n$ is enormous (billions of characters) and construction time dominates, production systems reach for SA-IS. Also, unlike a hash-based index (see Introduction to Hashing), the suffix array gives exact, worst-case guaranteed bounds with no probability of collision-driven failure, at the cost of the $O(\log n)$ or $O(n \log n)$ overhead hashing usually avoids for simple exact-match lookups — but hashing cannot efficiently answer range queries like "find all suffixes with a given prefix" or "find the longest repeated substring," which is precisely where the sorted suffix structure wins.

Take $S = \texttt{banana\$}$ (the sentinel `$` is smaller than any letter). Its 7 suffixes, indexed by start position:

Trace of prefix doubling (round by round). Round 0 ($k=1$, sort by 1 character): initial ranks by character: `$`=0, `a`=1, `b`=2, `n`=3. Rank array (by index):$[2,1,3,1,3,1,0]$. Sorting indices by this rank gives$SA = [6,1,3,5,0,2,4]$(ties among the three `a`-suffixes and two `n`-suffixes remain, broken arbitrarily but consistently at this stage). *Round 1 ($k=2$, key = (rank[i], rank[i+2])):* Using round-0 ranks, suffix 1 ("anana$") has key (rank[1], rank[3]) = (1,1); suffix 3 ("ana$") has key (rank[3], rank[5]) = (1,1) — still tied, correctly, since both share prefix "an". Suffix 5 ("a$") has key (1, rank[7]) = (1, -1) — distinguished from the others since it's shorter. After sorting by these pairs and reassigning ranks, "a$" (rank among the a-group: smallest, since -1 sorts first) separates from "ana$" and "anana$", which remain tied at this round because their first two characters "an" agree and the *next* pair also currently ties. *Round 2 ($k=4$):* now comparing 4-character prefixes via pairs built from round-1 ranks resolves "ana$" vs "anana$" (differing at position 4: "ana$" ends, "anana$" continues), and separates "nana$" from "na$" similarly. *Round 3 ($k=8 \geq n=7$):* loop condition fails to trigger further (rank already fully distinguishes all 7 suffixes at$k=4$, so the break condition `rank[SA[n-1]] == n-1` fires early) — final:

corresponding to suffixes: `$`, `a$`, `ana$`, `anana$`, `banana$`, `na$`, `nana$` — correctly sorted lexicographically (sentinel first, then the `a`-suffixes shortest-to-longest by shared-prefix rule, then `b`, then `n`-suffixes).

Kasai LCP pass, walking $i = 0,\dots,6$ in original text order (not sorted order), using `rankOfSuffix` (the inverse of $SA$):

Final $LCP = [0, 0, 1, 3, 0, 0, 2]$ (indexed by sorted rank, matching the figure above). The maximum LCP value is 3, at rank 3, confirming the longest repeated substring is "ana" — matching the figure's highlighted rows. A query for $P = \texttt{ana}$ binary-searches $SA$ and finds the contiguous block at ranks 2–3 (suffixes "ana$" and "anana$"), giving occurrence positions $\{3, 1\}$, exactly as read off the sorted suffix column.

The suffix tree was introduced by Peter Weiner in 1973 as the first linear-time construction of an index encoding all substrings of a text, though his original algorithm was memory-hungry and complex to implement. Edward McCreight simplified the construction in 1976, and Esko Ukkonen gave the now-standard online linear-time construction in 1995, building the tree incrementally character by character — a landmark in string algorithmics for its elegance and its amortized-analysis proof technique. The suffix array, designed explicitly as a space-efficient alternative, was introduced by Udi Manber and Gene Myers in 1990, alongside their $O(n \log n)$ doubling construction; Kasai, Lee, Arimura, Arikawa, and Park published the linear-time LCP-array construction in 2001, completing the suffix-array toolkit to match suffix-tree query power at a fraction of the memory.

Full-text search engines index large static corpora (source-code repositories, legal documents, literary corpora) using suffix-array-style structures to answer substring and phrase queries without scanning the whole corpus per query. Bioinformatics tools for genome alignment (short-read mappers, genome browsers) rely on the closely related Burrows–Wheeler transform and FM-index, both of which are built directly from the suffix array of the reference genome, to align millions of reads per run against multi-gigabase references. Data-compression algorithms such as bzip2 use the Burrows–Wheeler transform — itself computed from a sorted rotation array intimately related to the suffix array — as their core reversible transform before entropy coding. Plagiarism detectors and code-clone finders use the LCP array directly: the longest repeated substring and the longest common substring between two concatenated documents fall out of LCP maxima with almost no extra machinery. Version-control and diff tools, and biological repeat-finding pipelines (finding tandem repeats, transposable elements), similarly lean on suffix structures because they turn an $O(n^2)$ pairwise-comparison problem into an $O(n \log n)$ preprocessing step followed by linear-time repeat enumeration.

:::quiz[What does SA[i] store in a suffix array of length n?]

• The i-th character of the text
• The starting index of the i-th lexicographically smallest suffix ✓
• The length of the i-th suffix
• The hash value of the i-th suffix

:::quiz[What is LCP[i] conventionally defined as?]

• The length of the longest common prefix between suffix SA[i] and suffix SA[i+1]
• The length of the longest common prefix between suffix SA[i-1] and suffix SA[i] ✓
• The total number of distinct substrings up to position i
• The number of times character S[i] appears in the text

Ask the tutor: How would you extend a suffix array and LCP array to efficiently find the longest common substring shared across three or more input texts simultaneously?