Suffix Array Construction: Complete Implementation Guide

1. Introduction and Core Concepts

Suffix array construction is one of the most fundamental problems in string algorithms, forming the backbone of efficient text indexing, pattern matching, and compression. A suffix array for a string of length n is a permutation of the integers 0 to n-1 that represents the lexicographic order of all suffixes of the string. If we have the string "banana", its suffixes are "banana", "anana", "nana", "ana", "na", and "a". Sorting these lexicographically yields "a", "ana", "anana", "banana", "na", "nana", which corresponds to the suffix array [5, 3, 1, 0, 4, 2].

The concept was introduced by Manber and Myers in 1990 as a space-efficient alternative to suffix trees. While a suffix tree requires 20 to 50 times the size of the original text in memory and suffers from poor cache locality due to pointer chasing, a suffix array requires only an integer array of size n, typically 4n bytes, plus the text itself. This dramatic reduction in space made it possible to index gigabytes of text on commodity hardware, which was revolutionary for early web search engines and genomic databases. Today, suffix arrays are indispensable when you need to answer substring queries in logarithmic time without the memory overhead of a tree structure.

Formally, given a string S of length n over an alphabet Σ, we define SA as an array of length n such that S[SA[0]..n-1] < S[SA[1]..n-1] < ... < S[SA[n-1]..n-1] in lexicographic order. We assume a unique terminator character '$' that is lexicographically smaller than any other character is appended to S to ensure no suffix is a prefix of another. This sentinel guarantees a total order and simplifies construction algorithms. The inverse suffix array, ISA, where ISA[SA[i]] = i, is also frequently used to achieve constant-time rank queries. Together with the Longest Common Prefix (LCP) array, the suffix array can simulate any operation of a suffix tree while remaining far more cache-friendly and easy to serialize to disk.

Why Construction Matters

The naive way to build a suffix array — generate all suffixes and sort them with a standard comparison sort — takes O(n² log n) time because each string comparison can take O(n) time. For a 10 MB text file, this approach is completely infeasible. Therefore, the core challenge of suffix array construction is to sort n strings that share massive overlaps without explicitly comparing them character by character. Efficient construction algorithms exploit the fact that suffixes are not arbitrary strings; suffix i+1 is suffix i without its first character. This self-similarity allows for ingenious doubling and induced sorting techniques that reduce the problem to sorting integers.

Understanding construction is critical because the suffix array itself is not useful in isolation. Its power comes from how it is built and augmented. An incorrectly built array, for example one that mishandles the sentinel or fails to maintain stability during radix sorting, will return wrong binary search boundaries for pattern matching. In production systems like search engine inverted indexes or bioinformatics pipelines, a bug in construction propagates to every downstream query. Mastering the construction process gives you control over time-space trade-offs, from simple O(n log n) prefix-doubling implementations suitable for interviews to linear-time SA-IS implementations required for indexing the human genome.

2. How It Works

All efficient suffix array construction algorithms follow a common principle: transform the problem of sorting strings into the problem of sorting integers, then iteratively refine those integers until they represent the full lexicographic order. The most intuitive and widely taught method is prefix-doubling, also known as the doubling algorithm. The idea is to sort suffixes by their first 1 character, then by their first 2 characters, then 4, 8, and so on, doubling the prefix length each iteration. After log n iterations, the prefix length exceeds n, and the suffixes are fully sorted.

To achieve this without string comparisons, the algorithm maintains a rank array. Initially, rank[i] is simply the integer code of S[i] (for example, ord(S[i])). Suffixes are sorted by this single-character rank. In the next iteration, each suffix i is represented by a pair (rank[i], rank[i+k]), where k is the current prefix length. This pair captures the order of the first 2k characters: the first half is ranked by rank[i] and the second half by rank[i+k]. Sorting these pairs lexicographically gives the order for prefix length 2k. New ranks are then reassigned: suffixes with identical pairs get the same rank, otherwise they get increasing ranks. This process repeats with k doubling each time.

The key to making prefix-doubling fast is how the pairs are sorted. If we use a general-purpose comparison sort like Python's Timsort to sort the pairs, each iteration costs O(n log n), leading to an overall O(n log² n) algorithm. However, since the ranks are integers in the range [0, n-1], we can sort the pairs in O(n) time using radix sort — specifically, two passes of counting sort, first by the second key and then by the first key. This optimization yields the classic O(n log n) prefix-doubling algorithm, which is efficient enough for strings up to several million characters and is the standard interview-level implementation.

The Role of Induced Sorting

For truly linear-time construction, modern algorithms use induced sorting. The SA-IS (Suffix Array Induced Sorting) algorithm, developed by Nong, Zhang, and Chan in 2009, achieves O(n) time by classifying suffixes as L-type or S-type. A suffix is S-type if it is lexicographically smaller than the suffix starting at the next position, and L-type otherwise. The algorithm identifies LMS (Left-Most S-type) substrings, recursively sorts them, and then induces the order of all other suffixes in linear time by scanning the array forwards and backwards. While more complex to implement, SA-IS is the algorithm of choice in high-performance libraries like libdivsufsort and the basis for the SA construction in many genome assemblers.

Another linear-time approach is the DC3 (Difference Cover modulo 3) or Skew algorithm. DC3 divides suffixes into two groups: those starting at positions i where i mod 3 != 0, and those where i mod 3 == 0. It recursively sorts the first group by constructing a new string from triples of characters, then uses the sorted order to sort the remaining group via radix sort, and finally merges the two sorted groups. The elegance of DC3 lies in its divide-and-conquer structure and its guarantee of O(n) time even for large alphabets, but its constant factors and recursion overhead make it less practical than optimized prefix-doubling for moderate n.

3. Implementation

We will examine four implementations that represent a progression from clarity to performance. All code assumes the input string ends with a unique sentinel '$' that is smaller than any other character. In practice, you can append chr(0) or '$' if it does not occur in the text.

Naive O(n² log n) Construction

This implementation is only for educational comparison. It explicitly creates suffixes and sorts them, demonstrating why it fails for large n.

def build_suffix_array_naive(s):
    """Naive construction - O(n^2 log n). For teaching only."""
    n = len(s)
    # Create list of (suffix, starting_index)
    suffixes = [(s[i:], i) for i in range(n)]
    # Python's sort compares strings character by character
    suffixes.sort(key=lambda x: x[0])
    # Extract sorted indices
    sa = [idx for _, idx in suffixes]
    return sa

# Example
s = "banana$"
print(build_suffix_array_naive(s))  # [6, 5, 3, 1, 0, 4, 2]

Prefix-Doubling with Python Sort - O(n log² n)

This version implements the doubling idea using Python's built-in sort. It is concise, correct, and passes most interview tests for n up to 10⁵. Note the careful handling of out-of-bounds ranks with -1.

def build_suffix_array_doubling(s):
    """Prefix-doubling with comparison sort - O(n log^2 n)."""
    n = len(s)
    # Initial ranking by character code
    rank = [ord(c) for c in s]
    tmp = [0] * n
    sa = list(range(n))
    k = 1

    while True:
        # Sort by (rank[i], rank[i+k]) pair
        sa.sort(key=lambda x: (rank[x], rank[x + k] if x + k < n else -1))

        # Re-rank
        tmp[sa[0]] = 0
        for i in range(1, n):
            prev, cur = sa[i-1], sa[i]
            prev_key = (rank[prev], rank[prev + k] if prev + k < n else -1)
            cur_key = (rank[cur], rank[cur + k] if cur + k < n else -1)
            # Increase rank if pair is different
            tmp[cur] = tmp[prev] + (1 if prev_key < cur_key else 0)

        rank, tmp = tmp, rank

        # All ranks are distinct - done
        if rank[sa[n-1]] == n - 1:
            break
        k <<= 1  # Double prefix length: k = k * 2
        if k >= n:
            break
    return sa

Optimized Prefix-Doubling with Radix Sort - O(n log n)

To achieve true O(n log n) time, we replace the comparison sort with two passes of counting sort (radix sort). This is the version used in competitive programming and production systems where n is large. Counting sort is stable and runs in O(n + sigma) where sigma is the alphabet size.

def build_suffix_array_radix(s):
    """Prefix-doubling with radix sort - O(n log n)."""
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    tmp = [0] * n

    k = 1
    while True:
        # Key function for radix sort: sort by second key, then first key
        # First, sort by second key (rank[i+k])
        # Second key in range [-1, n-1] -> shift by 1 to make non-negative
        max_rank = max(rank) + 2  # +1 for shift, +1 for sentinel

        # Counting sort by second key
        cnt = [0] * max(max_rank, n + 1)
        for i in range(n):
            key = rank[i + k] + 1 if i + k < n else 0
            cnt[key] += 1
        for i in range(1, len(cnt)):
            cnt[i] += cnt[i-1]
        # Stable placement
        sa2 = [0] * n
        for i in range(n-1, -1, -1):
            idx = sa[i]
            key = rank[idx + k] + 1 if idx + k < n else 0
            cnt[key] -= 1
            sa2[cnt[key]] = idx
        sa = sa2

        # Counting sort by first key (rank[i])
        cnt = [0] * max(max_rank, n + 1)
        for i in range(n):
            cnt[rank[i] + 1] += 1
        for i in range(1, len(cnt)):
            cnt[i] += cnt[i-1]
        sa2 = [0] * n
        for i in range(n-1, -1, -1):
            idx = sa[i]
            key = rank[idx] + 1
            cnt[key] -= 1
            sa2[cnt[key]] = idx
        sa = sa2

        # Re-rank as before
        tmp[sa[0]] = 0
        for i in range(1, n):
            prev, cur = sa[i-1], sa[i]
            prev_pair = (rank[prev], rank[prev + k] if prev + k < n else -1)
            cur_pair = (rank[cur], rank[cur + k] if cur + k < n else -1)
            tmp[cur] = tmp[prev] + (1 if prev_pair < cur_pair else 0)
        rank, tmp = tmp, rank

        if rank[sa[n-1]] == n - 1:
            break
        k <<= 1
        if k >= n:
            break
    return sa

Kasai LCP and Pattern Search

A suffix array alone is often augmented with the LCP array and binary search for pattern matching. The Kasai algorithm builds LCP in O(n), and binary search finds any pattern P in O(|P| log n).

def build_lcp_kasai(s, sa):
    """Kasai algorithm - O(n) LCP construction."""
    n = len(s)
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i

    lcp = [0] * (n - 1)
    h = 0
    for i in range(n):
        r = rank[i]
        if r == 0:
            continue
        j = sa[r - 1]
        # Extend common prefix
        while i + h < n and j + h < n and s[i + h] == s[j + h]:
            h += 1
        lcp[r - 1] = h
        if h > 0:
            h -= 1
    return lcp

def pattern_search(s, sa, pattern):
    """Binary search for pattern in text using suffix array - O(m log n)."""
    n = len(s)
    m = len(pattern)
    lo, hi = 0, n
    # Lower bound
    while lo < hi:
        mid = (lo + hi) // 2
        # Compare pattern with suffix at sa[mid]
        suffix = s[sa[mid]:sa[mid] + m]
        if suffix < pattern:
            lo = mid + 1
        else:
            hi = mid
    left = lo
    hi = n
    while lo < hi:
        mid = (lo + hi) // 2
        suffix = s[sa[mid]:sa[mid] + m]
        if suffix <= pattern:
            lo = mid + 1
        else:
            hi = mid
    right = lo
    # All occurrences are sa[left:right] where suffix starts with pattern
    return sa[left:right] if s[sa[left]:sa[left]+m] == pattern else []

4. Step-by-Step Example

Let us walk through prefix-doubling construction for S = "banana$" (n=7, indices 0..6). The sentinel '$' has ASCII 36, smaller than 'a' (97). We will track SA, rank, and k at each iteration. This concrete trace is invaluable for debugging.

Initialization (k=1): We rank by single characters. Sorted characters are '$', 'a', 'a', 'a', 'b', 'n', 'n'. Their positions are 6, 5, 3, 1, 0, 4, 2. So initial SA = [6,1,3,5,0,2,4] is not yet fully sorted because suffixes starting with 'a' are not distinguished. Ranks are assigned by grouping equal characters: rank = [3,1,2,1,2,1,0] where rank[6]=0 for '$', rank[1]=rank[3]=rank[5]=1 for 'a', rank[2]=rank[4]=2 for 'n', rank[0]=3 for 'b'. Note that smaller rank means smaller character.

Iteration 1 (k=1, sorting by 2 characters): We sort by pairs (rank[i], rank[i+1]). The pairs are: i=0:(3,1) "ba", i=1:(1,2) "an", i=2:(2,1) "na", i=3:(1,2) "an", i=4:(2,1) "na", i=5:(1,0) "a$", i=6:(0,-1) "$". Sorting these pairs lexicographically gives order: (0,-1), (1,0), (1,2), (1,2), (2,1), (2,1), (3,1). Thus SA becomes [6,5,1,3,2,4,0]. New ranks: suffix 6 gets 0, suffix 5 gets 1, suffixes 1 and 3 share rank 2, suffixes 2 and 4 share rank 3, suffix 0 gets 4. So rank = [4,2,3,2,3,1,0].

Iteration 2 (k=2, sorting by 4 characters): Now pairs are (rank[i], rank[i+2]). For example, i=1: (2,2) representing "anan", i=3: (2,1) representing "ana$", i=5: (1,-1) representing "a$". Sorting gives SA = [6,5,3,1,0,2,4]. Let's verify: suffixes are "$", "a$", "ana$", "anana$", "banana$", "nana$", "na$". This is already the correct lexicographic order. New ranks become [4,2,3,2,3,1,0] -> after re-ranking, we get [4,2,3,2,3,1,0] with distinct values? Actually after this iteration, ranks are [4,2,3,2,3,1,0] -> recomputed as 0,1,2,3,4 distinct? Let's compute: pairs are (0,-1)=0, (1,-1)=1, (2,1)=2, (2,3)=3, (4,3)=4, (3,1)=? Wait precise re-ranking yields rank[6]=0, rank[5]=1, rank[3]=2, rank[1]=3, rank[0]=4, rank[4]=5, rank[2]=6. All ranks are distinct (0..6), so the algorithm terminates. The final SA [6,5,3,1,0,4,2] matches the expected order.

Iteration 3 (k=4): Would sort by 8 characters, but since all ranks are distinct, we stop early. This early termination is an important optimization — for many strings, especially those with small alphabets, the array becomes fully sorted long before k reaches n. In the worst case of a string like "aaaaa$", we need log n iterations because many suffixes share long prefixes.

Visual Trace Table

The progression can be summarized as the rank array evolving from coarse to fine. Each iteration doubles the resolution, similar to how a radix sort refines buckets. Debugging tip: print SA and rank after each iteration and verify that equal pairs receive equal ranks and that SA is stable.

5. Complexity Analysis

Complexity analysis for suffix array construction is nuanced because it depends heavily on the algorithm chosen and the alphabet size. The naive method is dominated by string comparison costs, while advanced methods are dominated by integer sorting and recursion overhead. Understanding these trade-offs is essential for selecting the right implementation for your constraints.

Best, average, and worst cases often coincide for deterministic construction algorithms, but the naive approach varies with input structure. A string with all distinct characters like "abcdef$" is easy for the naive method because comparisons terminate early, while a repetitive string like "aaaaa$" forces O(n) comparisons per pair. For prefix-doubling, performance is consistent regardless of input, but early termination can improve best-case behavior. Linear-time algorithms like SA-IS guarantee O(n) even in the worst case, though their constant factors are higher.

Space complexity is another critical dimension. All algorithms require O(n) additional space for SA and rank arrays, but SA-IS and DC3 need extra auxiliary arrays for bucket pointers and recursion stacks. In memory-constrained environments such as embedded systems or when indexing a 3 GB genome, the difference between 4n and 10n bytes can determine feasibility. External-memory variants exist that construct the suffix array using disk I/O in O(n log n) time with limited RAM.

For most practical purposes, the O(n log n) prefix-doubling with radix sort offers the best balance of simplicity and performance. It handles strings up to 10⁶ characters in well under a second in Python with PyPy optimizations, and up to 10⁷ in optimized C++. Only when indexing massive datasets like the human genome (3×10⁹ characters) or a web crawl does the linear-time guarantee of SA-IS become necessary to avoid the log n factor.

6. Variations and Optimizations

Beyond the basic prefix-doubling framework, several variations optimize for specific scenarios. One common improvement is to use a hybrid approach: start with prefix-doubling and switch to SA-IS for large n, or use multikey quicksort for the initial sorting of small buckets. Another optimization is to use the "doubling with early exit" technique where we track whether ranks are already distinct and terminate immediately, as shown in our implementation.

For integer alphabets where characters are already in the range [0, sigma-1], we can initialize ranks directly without sorting. For large alphabets like Unicode, we compress the alphabet first by sorting unique characters and mapping them to 0..sigma-1, which reduces the counting sort array size from 2¹⁶ to sigma. This alphabet compression step costs O(n log sigma) but pays off in every subsequent radix sort pass.

Cache efficiency is another major optimization. The standard prefix-doubling algorithm has poor locality because it accesses rank[i+k] with a stride of k that grows exponentially. To improve cache performance, some implementations store suffixes as 32-bit integers and use blocked sorting or use the "induced sorting" idea to sort suffixes in place. Libraries like SA-IS and divsufsort carefully arrange memory accesses to be sequential, which can yield 2-3x speedups on modern CPUs despite having the same asymptotic complexity.

Compressed and Enhanced Variants

The suffix array can be compressed to reduce space. A compressed suffix array (CSA) stores the array in n log sigma bits instead of n log n bits by using the psi function and wavelet trees. The FM-index, which combines the Burrows-Wheeler Transform with a sampled suffix array, can answer count and locate queries in compressed space and is the core data structure behind modern read aligners like BWA and Bowtie.

Enhanced suffix arrays augment SA with LCP and additional tables like the child table to simulate suffix tree traversals in O(1) time. This allows operations like finding the longest common substring of two strings, finding all maximal repeats, or computing the longest palindromic substring in linear time using only arrays. The child table can be built in O(n) from LCP using a stack, effectively giving you a suffix tree without pointers.

Parallel and external-memory constructions are also active research areas. Parallel prefix-doubling can be implemented with parallel radix sort using OpenMP or GPU kernels, achieving near-linear speedup on multi-core machines. External-memory algorithms like SA-DS and eSAIS construct suffix arrays for datasets larger than RAM by using disk-based sorting and merging, enabling indexing of terabyte-scale text collections on a single machine.

7. Real-World Applications

Suffix arrays are not just academic exercises; they power critical infrastructure across multiple domains. In web servers and search engines, they enable fast substring search over large document collections. While inverted indexes are preferred for word-based queries, suffix arrays are used for substring and wildcard queries, autocomplete, and plagiarism detection. For example, a code search engine that needs to find all occurrences of a function signature across millions of repositories can use a suffix array to answer queries in milliseconds instead of scanning every file.

In databases, suffix arrays accelerate LIKE '%pattern%' queries that cannot be served by B-trees. PostgreSQL's pg_trgm extension and Oracle's Oracle Text use suffix-array-like structures to index text columns for fast pattern matching. In bioinformatics, suffix arrays are fundamental to genome assembly and read alignment. The human genome is 3.2 billion base pairs; building a suffix array for it allows researchers to find all occurrences of a DNA read (100-300 bp) in O(m log n) time, which is essential for variant calling and gene annotation. Tools like MUMmer and STAR use enhanced suffix arrays to find maximal exact matches between genomes.

In networking and cybersecurity, suffix arrays are used for intrusion detection and data deduplication. Network intrusion detection systems need to scan packet payloads for thousands of malware signatures simultaneously; a suffix array of the payload can be searched for all signatures efficiently. Data deduplication systems, such as those in backup storage, use suffix arrays to find long repeated chunks across files to avoid storing duplicates, significantly reducing storage costs.

Data compression is another major application. The Burrows-Wheeler Transform, used in bzip2, is essentially the last column of the matrix of sorted rotations, which is directly derived from the suffix array. Building the BWT via SA is the first step in constructing the FM-index, which is a compressed self-index that can both store the text in compressed form and support pattern search without decompression. This is crucial for storing and querying massive text archives like Wikipedia or Common Crawl on limited storage.

8. Comparison with Alternatives

Choosing between suffix arrays and related structures depends on your priorities: memory, construction time, query time, and implementation complexity. Suffix trees offer faster queries but at a huge memory cost, while hash-based structures like suffix automata offer different trade-offs for substring existence versus enumeration.

Suffix trees provide O(m) pattern search (independent of n) compared to O(m log n) for suffix arrays, because they can walk the tree character by character. However, they require 20-50x the text size in pointers and are notoriously difficult to implement correctly, especially Ukkonen's linear-time construction. Suffix arrays, by contrast, are simple arrays that can be built with well-understood sorting primitives and are far more cache-efficient. For most applications where log n is small (n=10⁹, log n≈30), the O(m log n) vs O(m) difference is negligible compared to the memory savings.

Tries and hash tables are only suitable when you need to search for a predefined dictionary of patterns, not arbitrary substrings. A trie of all suffixes would be identical to a suffix trie and would require O(n²) space. Hashing with rolling hash (Rabin-Karp) can find patterns in O(n) average time but cannot enumerate all occurrences or support lexicographic queries like "find the k-th smallest suffix" or "find the longest repeated substring".

In practice, the decision tree is: if you need the absolute smallest memory and can tolerate slightly slower locate queries, use an FM-index. If you need to support complex string queries like finding all maximal repeats, longest common substring of multiple strings, or suffix tree traversals, use an enhanced suffix array. If you only need to check existence of substrings and n is moderate, a suffix automaton may be simpler. Only choose a suffix tree if you have a proven need for O(m) worst-case search and can afford the memory and implementation complexity — which is rare outside of specialized bioinformatics tools.

9. Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing suffix array construction. The most frequent mistake is mishandling the sentinel character. Forgetting to append a terminator or using a character that already appears in the text breaks the total order and causes suffixes that are prefixes of others to be ordered incorrectly. Always append a character smaller than any in the alphabet, such as chr(0) or '$' if '$' is guaranteed not to appear, and ensure your ranking treats out-of-bounds as -1, not 0, so that shorter suffixes sort before longer ones with the same prefix.

Another common pitfall is unstable sorting. When using radix sort, both counting sort passes must be stable; otherwise, the lexicographic order of pairs is destroyed. Implementing counting sort incorrectly by iterating forwards instead of backwards during placement, or by not correctly computing prefix sums, leads to an incorrectly sorted SA that may still look plausible for small tests but fails on larger random strings. Always test your implementation against the naive method for n up to 1000 on random strings with a fixed seed.

Off-by-one errors in rank updates are also prevalent. When re-ranking, you must compare the full pair (rank[i], rank[i+k]) for adjacent suffixes in SA order, not just rank[i]. A bug where you compare only the first component will assign the same rank to suffixes that differ in the second half, causing the algorithm to terminate prematurely with an incorrectly sorted array. Additionally, remember to copy ranks correctly: after computing tmp, you must swap rank and tmp references, not assign rank = tmp which would alias the arrays.

Best Practices for Production Code

• Alphabet compression: Map characters to 0..sigma-1 before construction to keep counting sort arrays small, especially for Unicode text.
• Use iterative doubling with early termination: Check if rank[SA[n-1]] == n-1 after each iteration to exit early; this often halves runtime on real data.
• Validate with brute force: For development, include an assertion that compares your SA against the naive SA for small n in debug builds.
• Handle large n with PyPy or C++: Python's recursion and sorting overhead limits n to ~200k for pure Python; for larger n, use library implementations like divsufsort or implement in C++.
• Build LCP together: Always build the LCP array immediately after SA using Kasai's algorithm; most queries require both, and building LCP later is wasteful.
• Consider memory layout: Store SA as array('i') or numpy array of dtype int32 for n < 2³¹ to halve memory versus Python lists of ints.

Finally, be mindful of Python's recursion limit and integer overflow when porting SA-IS or DC3 from C++. These algorithms are recursive and may exceed Python's default recursion depth of 1000 for large n. Either increase sys.setrecursionlimit or implement them iteratively. For interviews, the O(n log n) prefix-doubling with Python's sort is almost always sufficient and far less error-prone than attempting to code SA-IS from memory.

10. Interview Questions

Suffix array construction is a favorite topic for senior engineering interviews at companies that handle large-scale text processing. Interviewers use it to assess your understanding of sorting, string algorithms, and complexity trade-offs, not just your ability to memorize code. Below are common questions with guidance on how to answer them effectively.

Q1: How would you find the longest repeated substring in O(n log n) time?

Answer approach: Explain that after building SA and LCP, the longest repeated substring corresponds to the maximum value in the LCP array. The LCP array stores the longest common prefix between adjacent suffixes in SA order, so the maximum LCP is the longest substring that appears at least twice. Construction is O(n log n) for SA plus O(n) for Kasai, and scanning LCP for the maximum is O(n). Mention that to also return the substring itself, you take s[SA[idx]:SA[idx]+max_lcp] where idx is the position of the maximum. For bonus points, discuss how to find the longest repeated substring that appears at least k times using a sliding window minimum over LCP.

Q2: Why is a suffix array more memory-efficient than a suffix tree, and when would you still prefer a suffix tree?

Answer approach: Quantify the difference: SA needs 4n bytes (int32) versus 20-50n for a suffix tree due to nodes, edges, suffix links, and child pointers. SA is also cache-friendly because it is a contiguous array, while suffix tree traversal causes pointer chasing and cache misses. You would prefer a suffix tree only if you need O(m) worst-case pattern search independent of n and can afford the memory, or if you need to traverse the tree structure explicitly for problems like finding all maximal palindromes. In practice, an enhanced suffix array with LCP and child table can simulate any suffix tree operation with less memory, so suffix trees are rarely justified today.

Q3: How do you search for a pattern P in text T using a suffix array?

Answer approach: Describe binary search over SA. Since SA is sorted lexicographically, you can binary search for the lower bound (first suffix >= P) and upper bound (first suffix > P) using string comparison limited to |P| characters. Each comparison is O(m), and binary search takes O(log n) steps, so total is O(m log n). To find all occurrences, all suffixes in [lower, upper) start with P, and their SA values are the positions. Mention the optimization using LCP to achieve O(m + log n) with extra preprocessing (Manber-Myers search), and that in Python you can use bisect with a custom key.

Q4: What is the difference between O(n log n) prefix-doubling and O(n) SA-IS, and which would you implement in an interview?

Answer approach: Explain that prefix-doubling sorts pairs of ranks with doubling prefix length, using radix sort to achieve O(n log n) with simple code (~30 lines). SA-IS classifies suffixes into L/S types, sorts LMS substrings recursively, and induces the full order in O(n) but requires ~200 lines and careful handling of buckets. In an interview, always implement prefix-doubling with Python's sort (O(n log² n)) or radix sort (O(n log n)) because it is easy to code correctly under time pressure and demonstrates the core idea. Mention SA-IS only as theoretical knowledge to show depth, unless the interviewer explicitly asks for linear time.

Q5: How would you handle a text that does not fit in memory?

Answer approach: Discuss external-memory construction. For texts larger than RAM, you cannot hold SA in memory. Approaches include: (1) divide the text into blocks, build SA for each block, and merge using a k-way merge with LCP-aware comparison; (2) use the DC3 algorithm's divide-and-conquer which is naturally external-memory friendly; (3) use induced sorting with disk-based bucket sorting (eSAIS). Mention that practical tools like SA-IS for large genomes use disk-backed arrays and that the FM-index can be built from the BWT without ever holding the full SA in memory by using prefix-doubling with external sorting. This shows awareness of real-world scaling beyond textbook algorithms.