Suffix Array

The suffix array (SA) of a string S of length n is the lexicographically sorted permutation of the starting indices of all n suffixes of S. It is a compact (O(n) integers) substitute for the Suffix Tree that supports virtually the same query repertoire — substring search, longest repeated substring, longest common substring of two strings, distinct-substring counting — typically with a small log factor on queries but a 3–5× space saving and dramatically simpler implementation. The naive construction is O(n² log n) (sort n suffixes by string compare); the standard interview-friendly construction (a doubling/prefix-doubling sort) achieves O(n log² n) or O(n log n) depending on the inner sort; DC3 (Kärkkäinen-Sanders 2003) and SA-IS (Nong-Zhang-Chan 2009) achieve O(n) with non-trivial constants. Coupled with the LCP (Longest Common Prefix) array, computed in O(n) by Kasai et al. 2001, the suffix array becomes a substring-query Swiss army knife. Manber and Myers introduced the data structure in 1990 (the canonical SODA paper) explicitly to give the suffix-tree’s queries with an order-of-magnitude less memory.

1. Intuition — Sort Every Suffix and Index Them

A suffix of S is the string starting at some position i and running to the end: S[i..n-1]. There are exactly n of them (one per starting position). The suffix array SA[0..n-1] is the list of starting positions, sorted by the lexicographic order of the suffixes themselves. Equivalently, SA[k] = i means “the suffix starting at position i is the k-th smallest suffix of S in lexicographic order.”

Why is this useful? Because every substring of S is a prefix of some suffix. So if we sort all suffixes, then any pattern P we want to find in S will, if it occurs, appear as a prefix of a contiguous range of those sorted suffixes. We binary-search the suffix array for P (treating each suffix as if it were a key in a sorted dictionary), which takes O(|P| log n) comparisons. The suffix array is essentially “a sorted index over all substrings of S, packed into n integers.”

The real-world analogy: imagine you have a long book and you want to look up every occurrence of any phrase. You build an index that, for every position in the book, records “the rest of the book starting from this position, lexicographically.” Then sort that index alphabetically. To find every occurrence of “in the beginning,” you binary-search the sorted index for entries that start with “in the beginning” — they form a contiguous block, and the starting positions of those entries (the index values, not the suffixes themselves) are exactly your match positions.

The reason suffix arrays caught on after Manber-Myers 1990 is space. A Suffix Tree uses ~20·n bytes of memory in practice (pointers, child arrays); a suffix array uses ~5·n (one 32-bit integer per position, plus a similarly sized LCP array if you need richer queries). For genomic or large-text applications, that 4× constant matters more than the log factor it costs at query time.

2. Tiny Worked Example

Take S = "banana$" (length n = 7). The trailing $ is a sentinel — a character lexicographically smaller than every real character. It guarantees no suffix is a prefix of another, which simplifies sorting. Most production code appends a sentinel automatically.

The 7 suffixes (with their starting indices):

i	Suffix
0	banana$
1	anana$
2	nana$
3	ana$
4	na$
5	a$
6	$

Sort lexicographically (with $ < a < … < z):

Rank k	Suffix	Starting index = SA[k]
0	$	6
1	a$	5
2	ana$	3
3	anana$	1
4	banana$	0
5	na$	4
6	nana$	2

So SA = [6, 5, 3, 1, 0, 4, 2].

2.1 LCP array — the Longest Common Prefix between adjacent suffixes

The LCP array LCP[1..n-1] stores, for each consecutive pair of sorted suffixes, the length of their longest common prefix. (LCP[0] is undefined or zero by convention.)

k	suffix at SA[k]	LCP[k] = lcp(SA[k-1], SA[k])
0	$	—
1	a$	0 ($ and a$ share nothing)
2	ana$	1 (a is shared)
3	anana$	3 (ana is shared)
4	banana$	0 (anana$ and banana$ share nothing)
5	na$	0
6	nana$	2 (na shared)

So LCP = [0, 0, 1, 3, 0, 0, 2] (with LCP[0] filler).

The maximum value in LCP is 3, achieved between ana$ (index 3) and anana$ (index 1). That means the longest repeated substring in "banana$" is "ana", occurring at positions 3 and 1. This is one of the canonical SA + LCP applications: the longest repeated substring is always the deepest “shared prefix” between two adjacent sorted suffixes, computed in O(1) after building SA and LCP.

2.2 Substring search via SA

Suppose we want to find every occurrence of P = "an" in S = "banana". Binary-search the suffix array for the range where P is the prefix:

• P = "an" should sit between a$ (rank 1) and the suffixes starting with b....
• SA[2] = 3 → suffix "ana$" → starts with "an" ✓
• SA[3] = 1 → suffix "anana$" → starts with "an" ✓
• SA[4] = 0 → suffix "banana$" → does not start with "an".

So matches are at positions {3, 1}. The binary search did O(log n) suffix comparisons; each comparison is at most O(|P|) characters; total query cost: O(|P| log n).

(With LCP-array augmentation, this drops to O(|P| + log n) — see §6.1.)

3. Algorithm — Prefix-Doubling Construction

The simplest construction beyond “literally sort the suffixes” is prefix doubling (Manber-Myers): rank suffixes by their first 2^k characters, double k, repeat until the ranks are all distinct. After ⌈log₂ n⌉ rounds, every suffix has a unique rank → that ranking is the suffix array.

3.1 Pseudocode

SuffixArray(S):                                  # |S| = n; assume terminal sentinel appended
    n := |S|
    rank[i] := ord(S[i])     for i in 0..n-1     # initial rank = first-char value
    sa[i]   := i                                  # initial permutation

    k := 1
    while True:
        # Sort sa by the pair (rank[i], rank[i+k]) — the first 2k characters of suffix i.
        # rank[i+k] := -1 (or sentinel < anything) when i+k ≥ n.
        sort(sa, key = i -> (rank[i], rank[i+k] if i+k < n else -1))

        # Recompute ranks from the new sorted order, breaking ties by the pair-comparison.
        new_rank[sa[0]] := 0
        for j in 1..n-1:
            prev, curr := sa[j-1], sa[j]
            if (rank[prev], rank[prev+k] or -1) == (rank[curr], rank[curr+k] or -1):
                new_rank[curr] := new_rank[prev]
            else:
                new_rank[curr] := new_rank[prev] + 1
        rank := new_rank

        if rank[sa[n-1]] == n - 1:               # all ranks unique → done
            break
        k *= 2
    return sa

The clever invariant: after iteration k, suffixes are sorted by their first 2k characters. Each iteration doubles the comparison length; after log n iterations every suffix has a unique rank (since suffixes are distinct given the sentinel). With a comparison-based sort the per-iteration cost is O(n log n), total O(n log² n). Replacing the sort with Radix Sort on the integer pairs gives O(n log n) total.

3.2 LCP array via Kasai’s algorithm

Once SA is built, computing the LCP array between adjacent sorted suffixes is O(n) with a clever observation by Kasai et al. 2001:

KasaiLCP(S, sa):
    n := |S|
    rank[sa[k]] := k         for k in 0..n-1     # inverse permutation: rank[i] = position of suffix i in sa
    h := 0
    lcp := array of size n
    for i in 0..n-1:
        if rank[i] > 0:
            j := sa[rank[i] - 1]                  # the suffix immediately before suffix i in sorted order
            while i + h < n and j + h < n and S[i+h] == S[j+h]:
                h += 1
            lcp[rank[i]] := h
            if h > 0:
                h -= 1                             # the next suffix's LCP can drop by at most 1
        else:
            h := 0
    return lcp

The “h decreases by at most 1” observation is the magic: it bounds the total work in the inner while across all iterations of the outer for to O(n) by an amortized argument analogous to KMP’s. Without this trick, computing LCP would be O(n log n) or worse.

3.3 Full O(n) construction — DC3 and SA-IS

Two practical O(n) algorithms exist:

• DC3 (Difference Cover modulo 3), Kärkkäinen-Sanders 2003: sorts suffixes at positions ≡ 1, 2 mod 3 recursively, then merges with positions ≡ 0 mod 3. Elegant but with a sizable hidden constant; often slower than the O(n log n) doubling sort in practice for n up to a few million.
• SA-IS (Suffix Array — Induced Sorting), Nong-Zhang-Chan 2009: classifies each position by comparing its suffix to its right neighbour — suffix i is S-type (“Smaller”) if suffix(i) < suffix(i+1) and L-type (“Larger”) if suffix(i) > suffix(i+1) (the last position, the sentinel, is S-type by convention). It then recursively sorts only the LMS (“leftmost S-type”) positions — an S-type position whose left neighbour is L-type — and induces the full order of all L- and S-type suffixes from the sorted LMS suffixes in two O(n) left-to-right / right-to-left passes (per Nong, Zhang & Chan 2009). Currently the fastest known SA construction in practice; used in many production tools (libsais, libdivsufsort, sais-lite).

Both are implementation-grade, not interview-grade. Knowing they exist and citing them is enough; expect to implement only the doubling version live.

4. Python Implementation — O(n log² n) Prefix-Doubling

def build_suffix_array(s: str) -> list[int]:
    """Construct the suffix array of `s` via prefix-doubling.
 
    Time:  O(n log^2 n) using Python's sort.
    Space: O(n).
 
    Returns:
        sa[k] = the starting index of the k-th smallest suffix of s.
    """
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0] * n
 
    k = 1
    while True:
        # Sort indices by (rank[i], rank[i+k]); -1 acts as smallest sentinel for out-of-bounds.
        def key(i: int) -> tuple[int, int]:
            return (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)
 
        # Recompute ranks based on equality of adjacent pairs in the new sorted order.
        tmp[sa[0]] = 0
        for j in range(1, n):
            prev, curr = sa[j - 1], sa[j]
            tmp[curr] = tmp[prev] + (0 if key(prev) == key(curr) else 1)
        rank = tmp[:]
        if rank[sa[-1]] == n - 1:
            break
        k *= 2
 
    return sa
 
 
def build_lcp_array(s: str, sa: list[int]) -> list[int]:
    """Kasai's O(n) LCP construction.
 
    lcp[k] = length of longest common prefix between s[sa[k-1]:] and s[sa[k]:];
             lcp[0] is set to 0 (no predecessor for the smallest suffix).
    """
    n = len(s)
    inv = [0] * n
    for k in range(n):
        inv[sa[k]] = k
 
    lcp = [0] * n
    h = 0
    for i in range(n):
        if inv[i] > 0:
            j = sa[inv[i] - 1]
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[inv[i]] = h
            if h > 0:
                h -= 1
        else:
            h = 0
    return lcp
 
 
# Worked example from §2:
s = "banana$"
sa = build_suffix_array(s)
lcp = build_lcp_array(s, sa)
assert sa  == [6, 5, 3, 1, 0, 4, 2]
assert lcp == [0, 0, 1, 3, 0, 0, 2]
 
# Application: longest repeated substring
def longest_repeated_substring(s: str) -> str:
    sa = build_suffix_array(s)
    lcp = build_lcp_array(s, sa)
    if max(lcp) == 0:
        return ""
    k = max(range(len(lcp)), key=lambda i: lcp[i])
    return s[sa[k]:sa[k] + lcp[k]]
 
assert longest_repeated_substring("banana$") == "ana"

A few implementation notes:

• The tmp buffer avoids re-allocating the rank array each iteration.
• Using a tuple key for sa.sort() leans on Python’s TimSort. In a serious implementation we’d replace this with Counting Sort over the integer pairs to get O(n log n).
• The sentinel '$' in the worked example is critical to make all suffix ranks distinct after enough doublings. Without it, two suffixes where one is a prefix of the other (e.g., "a" and "ab") tie forever and the loop never terminates. In practice, append a character smaller than any in the alphabet (chr(0) works for byte strings).

5. Complexity

5.1 Construction

• Naive sort with string compare: O(n² log n) — n log n comparisons each costing up to n characters.
• Prefix-doubling with comparison sort: O(n log² n) — log n rounds, each doing an n log n sort of integer pairs.
• Prefix-doubling with Radix Sort on pairs: O(n log n) — log n rounds, each O(n) radix-sort.
• DC3 / SA-IS: O(n) — recursive structural construction. SA-IS is the fastest in practice as of 2026; DC3 is more pedagogically elegant.

For interview implementation, the O(n log² n) version is usually the right answer: it fits in 30 lines, runs fast enough on inputs up to ~10⁶, and is easy to debug. Quote the O(n) results as “exists in the literature” rather than implementing them live.

5.2 LCP array

O(n) via Kasai (§3.2). The inner-while bound comes from the fact that after h decreases at most by 1 per outer iteration, total decrements ≤ n, so total increments (= inner-while iterations) ≤ n + (initial 0) = O(n).

5.3 Query — substring search

• Binary search on SA without LCP: O(|P| log n) comparisons, each up to |P| characters → O(|P| log n) total.
• With LCP-array enhancement (Manber-Myers’ “LCP-LR” arrays): O(|P| + log n).
• With a precomputed Sparse Table over the LCP array (range-minimum queries in O(1)): query bounds tighten further to O(|P|) for very many lookups but the construction is more involved.

5.4 Space

• SA: O(n) integers.
• LCP: O(n) integers.
• For n integers stored as 32-bit values: ~4n bytes for SA + 4n for LCP = ~8n bytes — about 4× less than a Suffix Tree’s typical memory footprint.

6. Variants and Use Cases

6.1 Substring search in O(|P| + log n)

The naive O(|P| log n) binary search re-compares the prefix of P from scratch at each comparison. Manber-Myers’ refinement uses two auxiliary LCP arrays (LCP-L and LCP-R for left and right halves of the binary search) so that across the binary search, characters of P already-compared are not re-examined. The total comparisons drop to O(|P| + log n).

6.2 Longest common substring of two strings

Concatenate S = A + '#' + B + '$' (with # and $ two distinct characters not in either alphabet). Build SA + LCP. Find the maximum LCP value between two adjacent suffixes that come from different halves of S. That maximum is the length of the longest common substring; the substring itself is at the corresponding starting position. This generalizes to k strings (use distinct separators per string).

6.3 Distinct substring count

Each suffix contributes its own length — lcp[k] characters that overlap with the previous sorted suffix. Distinct substrings = Σ_{i=0..n-1} (n - sa[i]) − Σ_{k=1..n-1} lcp[k]. Computable in O(n) after SA + LCP.

6.4 Lexicographically k-th substring

Walk the suffix array in order and skip over already-counted prefixes via LCP; pinpoint the exact suffix and offset. O(n) per query, often O(log n) with binary indexed tree augmentation.

6.5 Burrows-Wheeler Transform

The BWT (the engine behind bzip2 compression and FM-indexes used in genomic search) is computed in O(n) once SA is known: BWT[k] = S[(SA[k] − 1) mod n]. The FM-index then turns BWT + a few small auxiliary arrays into a self-indexed compressed full-text search structure.

6.6 Z-array via SA

The Z-Algorithm’s output can be derived from SA + LCP in O(n), though for single-pattern matching the Z-algorithm directly is much simpler.

7. Comparison with Suffix Tree

Aspect	Suffix Tree	Suffix Array (+ LCP)
Memory (typical, 32-bit)	~20·n bytes	~8·n bytes (SA + LCP)
Construction time	O(n) (Ukkonen 1995, McCreight 1976)	O(n) (DC3, SA-IS) — but with bigger constants in practice
Substring search	O(|P|) per query	O(|P| + log n) with LCP-LR
Conceptual complexity	High (suffix links, edge labels, splitting)	Low (just a sorted array of integers)
Online (incremental)	Ukkonen is online	No good online SA construction
Best for	When asymptotically tight per-query latency matters	When memory matters more than per-query log factor

For typical interviews and contests, suffix arrays win on simplicity. Suffix trees are still the right answer when you need amortized-O(|P|) per query and online construction (e.g., adversarial-input streaming applications).

8. Pitfalls

8.1 Forgetting the sentinel

Without an end-of-string sentinel smaller than every real character, two suffixes where one is a prefix of the other (e.g., suffix at position 0 is "abc", suffix at position 5 is "abc") tie in the comparison forever, and the prefix-doubling loop fails to terminate. The fix is universal: append chr(0) or any guaranteed-smallest character.

8.2 Off-by-one in LCP indexing

Kasai’s lcp[rank[i]] indexes by the new (sorted) position of suffix i, not by i directly. Mixing the two indexings is a common implementation bug — the LCP array reads correctly but is permuted incorrectly relative to SA. Always check that lcp[k] corresponds to the gap between sa[k-1] and sa[k].

8.3 Quoting “O(n) construction” without attribution

DC3 and SA-IS achieve O(n) but with non-trivial constants. The textbook prefix-doubling SA is O(n log n) (with radix sort) or O(n log² n) (with comparison sort). When asked complexity, distinguish between “what I’m implementing” and “what’s known.”

8.4 Naive comparison-based sort hides complexity

Using Python’s list.sort with a string-prefix key looks fast but is actually O(n² log n) because each comparison is up to O(n) characters. Real prefix-doubling sorts integer-pair keys, not strings — reading “I sorted suffixes lexicographically” from a candidate is a red flag for the more careful interviewer.

8.5 Integer overflow on large strings

For n > 2³¹, 32-bit indices overflow. Production SA libraries use int64_t or templates over the index type. For interviews, this is unlikely to come up, but mention it for input sizes near the integer limit.

8.6 Using SA when a Trie or Suffix Tree is simpler

If the question is “match patterns from a small fixed dictionary against a stream,” a Trie or Aho-Corasick is usually simpler. SA shines for “given a big static text, answer many substring queries” — the offline indexing case. Picking SA when AC fits is technically correct but over-engineered.

9. Diagram — Suffix-Array + LCP Layout

graph LR
    subgraph "Sorted suffixes of banana$"
    A0["k=0: $              | sa=6 | lcp=0"]
    A1["k=1: a$             | sa=5 | lcp=0"]
    A2["k=2: ana$           | sa=3 | lcp=1"]
    A3["k=3: anana$         | sa=1 | lcp=3"]
    A4["k=4: banana$        | sa=0 | lcp=0"]
    A5["k=5: na$            | sa=4 | lcp=0"]
    A6["k=6: nana$          | sa=2 | lcp=2"]
    end
    A0 --> A1
    A1 --> A2
    A2 --> A3
    A3 --> A4
    A4 --> A5
    A5 --> A6

What this diagram shows. The seven sorted suffixes of "banana$" displayed in the order they appear in the suffix array (top to bottom = lexicographic ascending). Each row carries: the rank k, the suffix string, the value sa[k] (where in the original string this suffix starts), and the value lcp[k] (how many characters this suffix shares with the suffix above it). The arrows indicate “next in lexicographic order.” Two patterns are visible:

• The maximum LCP value (3, between rows k=2 and k=3) corresponds to the substring "ana", which is the longest repeated substring in the original string — a direct application of SA + LCP.
• Suffixes starting with the same letter cluster together (a-suffixes at rows 1–3, n-suffixes at rows 5–6), which is what enables binary-search substring lookup: any pattern’s matches form a contiguous range of sa[].

10. Common Interview Problems

LC# / Source	Problem	Use of SA
LC 1044	Longest Duplicate Substring	The canonical SA + LCP application — but binary search + Rabin-Karp also works.
LC 1923	Longest Common Subpath	Suffix automaton or SA + LCP on concatenation with separators.
LC 1408	String Matching in an Array	Naive solves it; SA is overkill but a valid showcase.
LC 718	Longest Common Substring	DP solves it for two strings; SA solves it for k strings.
Codeforces 271D	Good Substrings	SA + LCP gives distinct-substring count with extra constraints.
Codeforces 123D	String	Sum over all distinct substrings of (count of occurrences choose 2) — direct SA + LCP.
ICPC / SPOJ DISUBSTR	Number of Distinct Substrings	Definitive SA + LCP application.

Live-coding a working O(n log² n) SA + Kasai LCP under interview pressure is a high bar. Most interviewers ask the structure of SA + LCP and one application, not a full implementation.

11. Open Questions

• When exactly does SA-IS beat DC3 in practice? Reportedly always, but I haven’t reproduced the benchmark.
• Is there a clean online (incremental-character-append) suffix-array construction? Suffix trees have Ukkonen 1995; SA does not, to my knowledge.
• How does the LCP-LR augmentation compare to building a Sparse Table for RMQ over the LCP array? Both achieve O(|P| + log n) query but the sparse table is more general (supports arbitrary RMQ).

The memory figures used throughout this note are now pinned to a concrete model: storing the suffix array alone as n 32-bit integers is exactly 4n bytes; adding a 32-bit LCP array brings it to 8n bytes; a “careful” suffix-tree implementation is about 20n bytes (per Wikipedia’s Suffix array article, which cites the same 4n vs 20n comparison). All of these scale with the chosen integer width — n > 2³¹ forces 64-bit indices and doubles the constant — so quote them as “with 32-bit indices” rather than as absolute truths.

12. See Also

• Suffix Tree — the alternative with O(|P|) per-query but heavier memory
• Suffix Automaton — the third sibling: minimal DFA recognizing all substrings, O(n) construction, niche but powerful
• Knuth-Morris-Pratt — single-pattern alternative
• Z-Algorithm — equivalent linear-time alternative for single-pattern
• Rabin-Karp — randomized alternative with O(n + m) expected
• String Hashing — orthogonal substring tool
• Trie — prefix-tree relative
• Radix Sort — used inside O(n log n) SA construction
• Binary Search — used in SA query
• Big-O Notation
• SWE Interview Preparation MOC