Suffix Array: Complete Implementation Guide

1. Introduction and Core Concepts

A suffix array is one of the most elegant and powerful data structures in string processing. Formally, for a string S of length n, the suffix array is an array of integers SA[0..n-1] where SA[i] contains the starting position of the i-th lexicographically smallest suffix of S. In other words, if you list all n suffixes of a string, sort them alphabetically, and record only their starting indices, you get the suffix array. This compact representation captures the entire lexicographic order of all suffixes without explicitly storing the suffixes themselves.

The concept was introduced by Manber and Myers in 1990 as a space-efficient alternative to the suffix tree. 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 its pointer-heavy structure, a suffix array needs only an integer array of size n, typically 4n bytes. Despite this simplicity, it can answer almost any query a suffix tree can, often with only a logarithmic factor overhead. This trade-off between simplicity and power is why suffix arrays have become a cornerstone of modern string algorithms.

To understand why suffix arrays matter, consider the fundamental problem of substring search. Given a text T of length n and a pattern P of length m, determining whether P occurs in T and where it occurs is central to everything from text editors to genome analysis. A naive scan takes O(n * m) time. Preprocessing T into a suffix array allows us to answer this query in O(m log n) time using binary search, and with an auxiliary Longest Common Prefix (LCP) array, even in O(m + log n) time. For massive texts that are searched repeatedly, this preprocessing pays for itself immediately.

Core Terminology

Before diving deeper, it is essential to define the related concepts. A suffix of a string S = S[0..n-1] is any substring S[i..n-1] for 0 <= i < n. The empty suffix is usually ignored. The lexicographic order is the dictionary order based on the underlying alphabet, typically ASCII or Unicode code points. To ensure all suffixes are distinct and to simplify algorithms, we conventionally append a unique terminal character '$' that is lexicographically smaller than any other character in the alphabet. For example, the string "banana" becomes "banana$" with suffixes "banana$", "anana$", "nana$", "ana$", "na$", "a$", and "$".

The suffix array is almost always paired with the LCP array, also called the height array. LCP[i] stores the length of the longest common prefix between the suffixes starting at SA[i] and SA[i-1] for i > 0. This array is crucial for solving problems like finding the longest repeated substring, the longest common substring of two strings, and for accelerating pattern matching. Together, the suffix array and LCP array provide a complete and efficient toolkit for string analysis.

2. How It Works

The mechanism behind a suffix array relies on sorting suffixes efficiently without explicitly comparing entire suffixes from scratch each time. A naive approach that generates all suffixes as strings and sorts them with a standard comparison sort would take O(n^2 log n) time in the worst case, because comparing two suffixes can take O(n) time and there are O(n log n) comparisons. For a string of length 1,000,000, this is completely infeasible. The key insight of efficient suffix array construction is to use the fact that suffixes overlap heavily and to reuse previously computed information.

The classic O(n log n) doubling algorithm, also known as the prefix-doubling or Karp-Miller-Rosenberg algorithm, is the most instructive method. The idea is to sort suffixes by their first 1 character, then by their first 2 characters, then 4, then 8, and so on, doubling the prefix length each iteration. In each iteration, the ranking from the previous iteration is used to compare suffixes in O(1) time. A suffix S[i..] of length 2k can be seen as a pair: its first k characters (ranked in the previous step) and the k characters starting at i+k (also ranked). Thus, sorting suffixes by 2k-length prefixes reduces to sorting pairs of integers, which can be done with radix sort in O(n) time per iteration. Since we double k each time, there are O(log n) iterations.

Once the suffix array is built, searching is performed via binary search. Because the suffixes are sorted, we can binary search for a pattern P among them. At each step, we compare P with the suffix at the middle of the current search interval. If P is lexicographically smaller, we search the left half; if larger, the right half; if P is a prefix of the suffix, we have found an occurrence. This binary search requires O(log n) comparisons, each taking up to O(m) time, for a total of O(m log n). With the LCP array and techniques like the enhanced suffix array or using RMQ (Range Minimum Query), we can avoid re-comparing characters that have already been matched, reducing the search to O(m + log n).

The Role of Ranking and Radix Sort

The efficiency of the doubling algorithm hinges on two concepts: rank arrays and radix sort. The rank array R is the inverse of the suffix array: R[i] is the rank of the suffix starting at i among all suffixes. Initially, R[i] is simply the ASCII value of S[i]. After sorting by 2^k prefixes, R is updated so that suffixes with the same 2^k prefix get the same rank. This compression of a substring into a single integer rank is what allows O(1) comparison of pairs.

Radix sort is used because we are sorting pairs of integers (r1, r2) where both r1 and r2 are in the range [0, n-1]. A two-pass counting sort (first by the second key, then by the first key) sorts these pairs in O(n) time, which is faster than O(n log n) comparison sorting. This linear-time sorting per iteration is what brings the total complexity down to O(n log n) instead of O(n log^2 n).

3. Implementation

Implementing a suffix array correctly requires careful handling of indices, sentinel characters, and sorting stability. Below are several Python implementations progressing from naive to production-grade, each illustrating a different trade-off between clarity and performance. All code assumes the input string contains only characters greater than '$' and we append '$' internally if not present.

Naive Implementation for Clarity

This version is ideal for understanding the definition directly. It is easy to verify but should never be used for strings longer than a few thousand characters due to its quadratic behavior.

def suffix_array_naive(s: str) -> list[int]:
    # Append sentinel if not present to ensure distinct suffixes
    if not s.endswith('$'):
        s = s + '$'
    n = len(s)
    # Generate all suffixes with their starting index
    # Sorting uses Python's Timsort which compares suffix strings directly
    suffixes = [(s[i:], i) for i in range(n)]
    suffixes.sort(key=lambda x: x[0])
    # Extract only the sorted indices
    sa = [idx for _, idx in suffixes]
    return sa

# Example: suffix_array_naive("banana") -> [6, 5, 3, 1, 0, 4, 2]
# Suffixes sorted: $, a$, ana$, anana$, banana$, na$, nana$

Efficient O(n log n) Doubling Algorithm

This is the standard implementation for competitive programming and most practical applications. It uses the prefix-doubling technique with Python's sort for simplicity; a true O(n log n) version would replace the sort with radix sort, but Python's sort is highly optimized and often fast enough for n up to 200,000.

def suffix_array_doubling(s: str) -> list[int]:
    if not s.endswith('$'):
        s = s + '$'
    n = len(s)
    # k is the current prefix length being sorted (1, 2, 4, 8, ...)
    k = 1
    # Initial ranking based on single characters
    rank = [ord(c) for c in s]
    tmp = [0] * n
    sa = list(range(n))

    while True:
        # Sort by (rank[i], rank[i+k]) pair
        # Use -1 for rank beyond string end to make shorter suffixes smaller
        sa.sort(key=lambda x: (rank[x], rank[x + k] if x + k < n else -1))

        # Recompute temporary ranks after sorting
        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)
            tmp[cur] = tmp[prev] + (prev_key < cur_key)
        
        rank, tmp = tmp, rank
        # If all ranks are distinct, we are done
        if rank[sa[-1]] == n - 1:
            break
        k <<= 1  # Double k for next iteration
        if k >= n:
            break
    return sa

Kasai's Algorithm for LCP Array

The LCP array is built in linear time from the suffix array and the original string using Kasai's algorithm. It exploits the fact that if LCP between suffix i and its predecessor is h, then LCP for suffix i+1 will be at least h-1.

def build_lcp_array(s: str, sa: list[int]) -> list[int]:
    if not s.endswith('$'):
        s = s + '$'
    n = len(s)
    # rank[i] is the position of suffix i in sa
    rank = [0] * n
    for i, suffix_idx in enumerate(sa):
        rank[suffix_idx] = i

    lcp = [0] * n
    h = 0  # Current LCP length
    for i in range(n):
        r = rank[i]
        if r > 0:
            j = sa[r - 1]  # Previous suffix in sorted order
            # Extend h as long as characters match
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[r] = h
            if h > 0:
                h -= 1  # Key optimization: h decreases by at most 1
    return lcp
# lcp[0] is always 0 (no predecessor)

Pattern Search Using Binary Search on Suffix Array

Once SA is built, we can find all occurrences of a pattern. This implementation finds the lower and upper bounds of the interval containing the pattern.

def find_pattern(s: str, pattern: str, sa: list[int]) -> list[int]:
    if not s.endswith('$'):
        s = s + '$'
    n = len(s)
    m = len(pattern)

    # Helper to compare pattern with suffix starting at idx
    def compare(idx: int) -> int:
        # Returns -1 if pattern < suffix, 0 if pattern is prefix of suffix, 1 if pattern > suffix
        suffix = s[idx:]
        # Only compare up to m characters
        if suffix[:m] == pattern:
            return 0
        return -1 if pattern < suffix[:m] else 1

    # Find lower bound (first suffix >= pattern)
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if compare(sa[mid]) <= 0:  # pattern <= suffix
            hi = mid
        else:
            lo = mid + 1
    left = lo

    # Find upper bound (first suffix > pattern)
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if compare(sa[mid]) < 0:  # pattern < suffix
            hi = mid
        else:
            lo = mid + 1
    right = lo

    # All suffixes in [left, right) have pattern as prefix
    if left < right and s[sa[left]:sa[left]+m] == pattern:
        return sorted([sa[i] for i in range(left, right)])
    return []

4. Step-by-Step Example

Let us walk through the construction of the suffix array for the classic example S = "banana". We will append the sentinel to get S = "banana$". The length n is 7. This example is small enough to trace manually but rich enough to show repeated substrings and overlapping suffixes.

First, we list all suffixes with their starting indices: 0: "banana$", 1: "anana$", 2: "nana$", 3: "ana$", 4: "na$", 5: "a$", 6: "$". If we sort these suffixes lexicographically, we compare them character by character. "$" is smallest because sentinel is smallest. Next, "a$" is smaller than "ana$" because 'a' is equal but '$' (end of "a$") is smaller than 'n'. Similarly, "ana$" is smaller than "anana$" for the same reason. Continuing this, the sorted order becomes: "$" (6), "a$" (5), "ana$" (3), "anana$" (1), "banana$" (0), "na$" (4), "nana$" (2). Therefore, the suffix array is SA = [6, 5, 3, 1, 0, 4, 2].

Now let us trace the doubling algorithm on "banana$". Initially k=1, rank is based on characters: '$'=36, 'a'=97, 'b'=98, 'n'=110. So rank = [98, 97, 110, 97, 110, 97, 36]. SA sorted by first character gives [6, 1, 3, 5, 0, 2, 4] (all 'a's together, then 'b', then 'n's). We assign new ranks: rank[6]=0, rank[1]=1, rank[3]=1, rank[5]=1, rank[0]=2, rank[2]=3, rank[4]=3. Note that suffixes starting at 1,3,5 all share rank 1 because they start with 'a'.

Next iteration k=2. We sort by pairs (rank[i], rank[i+2]). For i=5, the pair is (1, 0) because rank[5]=1 and rank[7] is out of bounds (-1, treated as -1 but normalized to 0 after ranking). For i=3, pair is (1, 3) because rank[3]=1 and rank[5]=1 (wait, rank[5] is 1, but we need rank[i+k] = rank[5]=1). Actually with proper mapping, the pairs become: 6:(0,-1), 5:(1,-1), 3:(1,3), 1:(1,3), 0:(2,3), 4:(3,-1), 2:(3,3). Sorting these pairs yields SA = [6, 5, 3, 1, 0, 4, 2] which is already the final correct order. The algorithm detects that all ranks are distinct after recomputing and terminates. This demonstrates how doubling quickly converges.

LCP Array for "banana$"

Using SA = [6,5,3,1,0,4,2], we compute LCP. Compare suffix 5 ("a$") with predecessor 6 ("$"): LCP=0. Compare suffix 3 ("ana$") with predecessor 5 ("a$"): they share 'a' then differ ('n' vs '$'), so LCP=1. Compare suffix 1 ("anana$") with predecessor 3 ("ana$"): they share "ana", so LCP=3. Compare suffix 0 ("banana$") with predecessor 1: LCP=0. Compare suffix 4 ("na$") with predecessor 0: LCP=0. Compare suffix 2 ("nana$") with predecessor 4 ("na$"): they share "na", so LCP=2. Thus LCP = [0, 0, 1, 3, 0, 0, 2]. This array tells us that the longest repeated substring is "ana" with length 3.

5. Complexity Analysis

Understanding the complexity of suffix array operations is critical for choosing the right construction algorithm and for predicting performance on large inputs. The naive method, while simple, is prohibitively expensive for large n. The doubling algorithm offers a good balance, while linear-time algorithms like SA-IS and DC3 (Skew) achieve optimal asymptotic complexity at the cost of implementation complexity.

Construction time dominates the cost. Query time after construction is typically logarithmic or linear in the pattern length, making suffix arrays ideal for scenarios with many queries on a static text. Space is always O(n) for the array itself, plus O(n) for the LCP array and rank array if needed. The constant factors matter: an integer array of size 10 million uses about 40 MB, which fits in memory on modern servers but may be heavy for embedded systems.

The table below summarizes the complexities for the most common operations. Note that "Construction" refers to building SA alone; building LCP adds O(n) time and space.

In practice, the doubling algorithm with radix sort is often the sweet spot. For n = 1e6, O(n log n) with a small constant is easily fast enough in PyPy or C++ (under 2 seconds), while a linear algorithm might be only marginally faster but far harder to implement correctly. For Python specifically, using the built-in sort with key as a tuple is O(n log^2 n) but benefits from highly optimized C implementation, often outperforming a pure-Python radix sort for n < 500,000. Always benchmark on your target data size and alphabet.

Space Considerations

Space is where suffix arrays shine compared to suffix trees. A suffix array needs exactly n integers. With 32-bit integers, this is 4n bytes; with 64-bit for texts larger than 2^31, it is 8n bytes. The LCP array adds another 4n bytes, and the rank array another 4n bytes during construction (can be discarded after). In total, a fully enhanced suffix array uses about 12n bytes. A suffix tree, by contrast, needs at least 20n bytes for its nodes, edges, and suffix links, often more. For a 1 GB genome, a suffix array needs ~4 GB, while a suffix tree would need >20 GB and likely not fit in RAM.

6. Variations and Optimizations

The basic suffix array can be enhanced in several ways to improve construction speed, query speed, or functionality. These variations are important for production systems handling large-scale data.

The most significant optimization is the use of induced sorting, as seen in the SA-IS (Suffix Array - Induced Sorting) algorithm. SA-IS achieves linear time by recursively sorting a subset of suffixes (the LMS suffixes) and then inducing the order of the remaining suffixes. It is the fastest known algorithm in practice for large alphabets and is used in libraries like libdivsufsort. The DC3 (Difference Cover modulo 3) or Skew algorithm is another linear-time method that is easier to understand: it sorts suffixes starting at positions i mod 3 != 0 recursively, then merges with the remaining suffixes. Both algorithms are complex to implement but guarantee O(n) worst-case time.

For query optimization, the Enhanced Suffix Array (ESA) augments SA and LCP with additional tables like the child table and suffix link table, allowing it to simulate any suffix tree traversal in O(1) per step. This makes operations like finding the longest common substring of two strings or enumerating all repeats as fast as with a suffix tree but with far less memory. Another common optimization is to use a compressed suffix array (CSA) or FM-index, which compresses the suffix array using the Burrows-Wheeler Transform (BWT) to achieve space close to the entropy of the text while still supporting search. This is critical for indexing the human genome (3 billion characters) on a single machine.

Practical Python Optimizations

In Python, the biggest bottleneck is the sorting step. To speed up the doubling algorithm, you can use the library function sorted with a key that is a tuple of two integers, but this creates many temporary tuples. A faster approach is to use NumPy or to implement counting sort manually when the rank range is small. For very large strings, consider using the PyPy interpreter or delegating construction to a C extension like pydivsufsort. Another trick is to use prefix-doubling with early termination: if the maximum rank equals n-1, all suffixes are distinct and you can stop, which often happens well before log n iterations for random strings.

Memory optimization is also crucial. Instead of storing the entire string plus sentinel as a Python string (which uses 1-4 bytes per character depending on Unicode), you can store it as a bytes object or array('i') for ASCII texts. Using array('I') or list of ints for SA is standard, but for n > 10^7, consider using numpy.ndarray with dtype np.int32 to save memory and improve cache performance.

7. Real-World Applications

Suffix arrays are not just theoretical curiosities; they are deployed in some of the most demanding data processing pipelines in the world. Their ability to index massive strings for fast substring queries makes them indispensable.

In bioinformatics, suffix arrays and their compressed variants (FM-index) are the backbone of modern DNA sequence aligners. Tools like Bowtie, BWA, and HISAT2 index the 3-billion-base-pair human genome using an FM-index derived from the suffix array, allowing them to align billions of short reads (100-150 bp) per day. Finding the longest common substring between two genomes, detecting repeats, and assembling genomes from fragments all rely on LCP array queries. Without suffix arrays, the Human Genome Project and modern personalized medicine would be computationally infeasible.

In web search and information retrieval, suffix arrays are used for substring search in large document collections, for plagiarism detection, and for building inverted indexes. Search engines use suffix arrays to implement "search as you type" and to find near-duplicate documents by looking for long common substrings. Databases like PostgreSQL use suffix arrays internally for full-text search and for indexing large text columns with trigram indexes that are conceptually related.

Other domains include data compression (the Burrows-Wheeler Transform, used in bzip2, is essentially a reordering of characters based on suffix array order), version control systems (finding diffs between files by finding longest common subsequences), and network intrusion detection (searching packet payloads for virus signatures). Even text editors like VS Code and Sublime Text use suffix-array-like structures for fast find-all operations on large files.

8. Comparison with Alternatives

Suffix arrays are one of several string indexing structures. Choosing the right one depends on your constraints regarding memory, construction time, query time, and implementation effort. The main alternatives are suffix trees, suffix automata (SAM), tries, and hash-based indexes.

A suffix trie is the simplest: it is a trie containing all suffixes. It is easy to understand but uses O(n^2) space in the worst case and is never used for large texts. A suffix tree compresses the trie by merging nodes with single children, achieving O(n) space and O(m) search time, which is theoretically optimal. However, its large constant factor, poor locality, and complex implementation make it less popular today. A suffix automaton (also called DAWG) is a minimal DFA that recognizes all substrings; it also has O(n) space and O(m) search but cannot directly enumerate occurrences without extra structures. Hash-based methods like rolling hash with binary search or suffix hashing offer O(1) average search but suffer from collisions and cannot support lexicographic queries like finding all suffixes in a range.

The suffix array strikes the best balance for most use cases: it is simple to implement, has excellent cache performance due to its array layout, uses minimal memory, and supports almost all operations that suffix trees do with only a log factor overhead, which can be removed with LCP+RMQ. For these reasons, most modern libraries and competitive programmers prefer suffix arrays over suffix trees.

In summary, if you need the absolute fastest substring search and can afford the memory and implementation complexity, a suffix tree is optimal. If you need to count distinct substrings or build a minimal automaton, SAM is ideal. For everything else, especially in Python or when memory is limited, the suffix array is the recommended default.

9. Common Mistakes and Best Practices

Implementing suffix arrays is riddled with subtle off-by-one errors and performance pitfalls. Awareness of these common mistakes can save hours of debugging.

The most frequent mistake is forgetting the sentinel character. Without a unique terminator smaller than all other characters, suffixes that are prefixes of other suffixes (e.g., "a" and "ana") will not be ordered correctly, and the doubling algorithm may fail to assign distinct ranks. Always append '$' or chr(0) and ensure your ranking handles the out-of-bounds case as -1. A related mistake is using a sentinel that actually appears in the text; this breaks the distinctness guarantee. If your text can contain any Unicode character, use a separate integer array with a sentinel value of -1 instead of a character.

Another common error is incorrect handling of the rank array during doubling. Beginners often forget to recompute ranks after sorting or use an unstable sort that breaks the tie-breaking logic. The rank update must be: tmp[sa[0]] = 0; for i from 1 to n-1, tmp[sa[i]] = tmp[sa[i-1]] + (pair[i-1] < pair[i]). If you use Python's sort, it is stable, but if you implement counting sort, you must ensure it is stable as well (sort by second key first, then first key). Also, remember to swap rank and tmp correctly and to double k each iteration; failing to double leads to infinite loops.

Performance pitfalls include using string slicing s[i:] inside the comparison function during binary search, which creates O(n) copies per comparison and leads to O(m n log n) time. Instead, compare character by character without slicing, or use s.startswith(pattern, idx) or direct indexing. For large alphabets, not using radix sort can make construction O(n log^2 n) and too slow for n > 200k. Finally, recursion depth can be an issue for linear algorithms like SA-IS if implemented recursively in Python; use iterative versions or increase recursion limit.

Best Practices Checklist

• Always validate your SA by checking that suffixes are sorted: for i in range(n-1): assert s[sa[i]:] <= s[sa[i+1]:]
• Write a brute-force validator for small n and test against the naive implementation on random strings.
• Use 0-based indexing consistently and document whether your SA includes the sentinel suffix.
• For production code, use a well-tested library like pydivsufsort or libsais bindings instead of rolling your own for n > 1e6.
• Profile memory usage: use sys.getsizeof and consider array('I') or numpy for large arrays.
• When building LCP, ensure you handle the case rank[i] == 0 (no predecessor) to avoid index errors.

10. Interview Questions

Suffix arrays are a favorite topic in advanced algorithm interviews for roles involving string processing, bioinformatics, or search infrastructure. Interviewers expect you to know not just the definition but also construction, LCP, and applications. Below are common questions with high-level answers.

Q1: How would you find the longest repeated substring in a string using a suffix array?

Answer: Build the suffix array and the LCP array. The longest repeated substring corresponds to the maximum value in the LCP array, because LCP[i] is the longest common prefix between two adjacent suffixes in sorted order, and any repeated substring must be a prefix of some suffix and thus appear as a common prefix of two suffixes. The answer is the substring s[sa[idx]: sa[idx]+max_lcp] where idx is the index of the maximum LCP value. This runs in O(n log n) for SA construction plus O(n) for scanning LCP, overall O(n log n). For "banana$", max LCP is 3 at index 3, corresponding to "ana". Be prepared to explain Kasai's algorithm for LCP and why the maximum adjacent LCP is sufficient (any non-adjacent pair's LCP is the minimum of the interval between them, so it cannot exceed the maximum adjacent).

Q2: Given two strings A and B, how do you find their longest common substring efficiently?

Answer: Concatenate the strings with distinct sentinels: S = A + '#' + B + '$', where '#' and '$' are characters smaller than any in A or B and '#' != '$'. Build the suffix array and LCP array for S. Then scan the LCP array and consider only adjacent pairs where one suffix comes from A and the other from B (i.e., sa[i] < len(A) and sa[i-1] > len(A) or vice versa). The maximum LCP among such pairs is the length of the longest common substring, and the substring itself can be recovered. This works because any common substring is a prefix of a suffix from each string, and those suffixes will be adjacent in the sorted order after accounting for other suffixes. Complexity is O((n+m) log (n+m)). An alternative is to use binary search + hashing, but the SA method also enumerates all common substrings.

Q3: What is the difference between a suffix array and a suffix tree, and when would you prefer one over the other?

Answer: Both index all suffixes, but a suffix tree is a compressed trie with O(n) nodes and edges, supporting O(m) search, while a suffix array is a sorted array of suffix indices using O(n) integers and O(m log n) search (or O(m + log n) with LCP). Suffix arrays use 4-5x less memory, have better cache locality, and are simpler to implement. Suffix trees are faster for search and can support more complex operations like online construction (Ukkonen). Prefer suffix arrays when memory is constrained, when you need simplicity, or when you have many queries on a static text (typical in bioinformatics and search). Prefer suffix trees when you need worst-case O(m) search or online updates. In practice, enhanced suffix arrays can simulate suffix trees, making SA the default choice.

Q4: How do you count the number of distinct substrings of a string using its suffix array?

Answer: The total number of substrings (including duplicates) is n*(n+1)/2. The number of distinct substrings is this total minus the sum of LCP values. Reason: each suffix of length L contributes L new substrings, but LCP[i] of them are already counted as prefixes of the previous suffix in sorted order. So distinct = sum_{i=0}^{n-1} (n - sa[i]) - sum_{i=1}^{n-1} lcp[i]. For "banana$" (n=7), total substrings = 28, sum LCP = 0+1+3+0+0+2=6, distinct = 28-6=22 (including those with $; for "banana" alone, subtract sentinel contributions). This is a classic application that tests understanding of LCP. It can be computed in O(n) after SA+LCP are built.

Q5: How would you handle a very large string (e.g., 10 GB) that does not fit in memory?

Answer: For external memory, use a divide-and-conquer or induced sorting approach that works in chunks, or use a compressed suffix array / FM-index that is built in a streaming fashion. One approach is the DC3/Skew algorithm which is naturally external-memory friendly. Another is to use prefix-doubling with external sorting (sort pairs using external merge sort). Alternatively, build the Burrows-Wheeler Transform directly via SA-IS in external memory and then use an FM-index for queries, which needs only the BWT and rank structures (much smaller). In practice, you would use a distributed framework like Spark to build SA in parallel or use a library like divsufsort with memory-mapped files. The key is to avoid O(n^2) memory and to use disk-backed sorting.