Suffix Arrays and Trees

The previous four algorithms preprocessed the pattern; the text was scanned from scratch on every search. This is the right balance for one-time searches.

The balance reverses when thousands of queries are made against the same text: the text can be preprocessed once, and queries answered at a cost that depends not on the text’s length but on the pattern’s. This lesson builds those structures.

The Suffix Array

All of a text’s suffixes are sorted, and only their starting positions are stored. The resulting array of integers is called a suffix array.

def suffix_array(text: str) -> list[int]:
    """Starting positions that arrange the suffixes in lexicographic order."""
    return sorted(range(len(text)), key=lambda i: text[i:])


text = "banana"
sa = suffix_array(text)
print(sa)                              # [5, 3, 1, 0, 4, 2]
print([text[i:] for i in sa])
# ['a', 'ana', 'anana', 'banana', 'na', 'nana']

The structure holds only $n$ integers; the text itself is stored once. The memory cost is far lower than storing the suffixes separately.

The construction above is $O(n^2 \log n)$, because it reads $O(n)$ characters per comparison, and it is meant only to illustrate the idea. A suffix array is built in $O(n \log n)$ with the method that doubles the compared length at each round, and in $O(n)$ with more advanced methods.

Query

Because the suffixes are sorted, the suffixes that start with the pattern occupy a contiguous range in the array. Binary search gives the boundaries of that range.

def match_range(text: str, sa: list[int], pattern: str) -> tuple[int, int]:
    """The [start, end) range in the suffix array of suffixes starting with pattern."""
    m = len(pattern)

    lo, hi = 0, len(sa)
    while lo < hi:                                  # lower bound
        mid = (lo + hi) // 2
        if text[sa[mid]:sa[mid] + m] < pattern:
            lo = mid + 1
        else:
            hi = mid
    start = lo

    lo, hi = start, len(sa)
    while lo < hi:                                  # upper bound
        mid = (lo + hi) // 2
        if text[sa[mid]:sa[mid] + m] <= pattern:
            lo = mid + 1
        else:
            hi = mid
    return start, lo


long_text = "ABABDABACDABABCABAB"
long_sa = suffix_array(long_text)

start, end = match_range(long_text, long_sa, "ABAB")
print(end - start, sorted(long_sa[start:end]))     # 3 [0, 10, 15]

start, end = match_range(long_text, long_sa, "ZZ")
print(end - start)                                  # 0

Every step of the binary search compares up to $m$ characters; query cost is $O(m \log n)$. The occurrence count, on the other hand, is read from the width of the range in a single operation — finding how many times a pattern occurs does not require scanning the text.

Comparing the two costs makes the trade-off visible: KMP pays $O(n + m)$ on every query; the suffix array pays $O(n \log n)$ once, then answers every query at $O(m \log n)$. The second path wins as the number of queries grows — the text-side counterpart of the preprocessing pattern from the Time and Space Trade-off lesson.

The Longest Common Prefix Array

The suffix array is incomplete on its own; knowing the overlap between neighboring suffixes answers many more questions.

The LCP array holds the length of the longest common prefix of two consecutive suffixes in the sorted order. Kasai’s method computes it in $O(n)$.

def lcp_array(text: str, sa: list[int]) -> list[int]:
    """lcp[k]: the common-prefix length of the suffixes sa[k-1] and sa[k]."""
    n = len(text)
    rank = [0] * n
    for k, i in enumerate(sa):
        rank[i] = k

    lcp = [0] * n
    h = 0
    for i in range(n):
        if rank[i] > 0:
            j = sa[rank[i] - 1]
            while i + h < n and j + h < n and text[i + h] == text[j + h]:
                h += 1
            lcp[rank[i]] = h
            if h:
                h -= 1                 # the next suffix carries at least h-1 common prefix
        else:
            h = 0
    return lcp


print(lcp_array("banana", sa))        # [0, 1, 3, 0, 0, 2]

The array’s largest value gives the longest piece that occurs twice in the text.

def longest_repeat(text: str) -> str:
    sa = suffix_array(text)
    lcp = lcp_array(text, sa)
    k = max(range(len(lcp)), key=lambda i: lcp[i])
    return text[sa[k]:sa[k] + lcp[k]]


print(longest_repeat("banana"))                # ana
print(longest_repeat("ABABDABACDABABCABAB"))   # ABAB

The same structure answers other questions as well: the longest common piece of two texts (by concatenating them and treating them as one), the number of distinct substrings, and repeat detection in compression.

The Suffix Tree

A suffix tree is a compressed trie containing all of a text’s suffixes: chains of single-child nodes are merged, and edges represent subranges of the text.

It carries the same information as the suffix array, arranged differently:

Criterion	Suffix array	Suffix tree
Construction	$O(n)$ (advanced methods)	$O(n)$
Query	$O(m \log n)$	$O(m)$
Memory constant	Small ($n$ integers)	Large (nodes and pointers)
Implementation	Simple	Complex

The logarithmic factor in query cost can also be removed by adding LCP information to the suffix array. In practice the suffix array is preferred: its memory constant is small and its code is easier to check. The suffix tree stands out in theoretical analyses that need the tree structure itself, and in certain specialized queries.

A third structure in the same family is the suffix automaton: the smallest automaton that recognizes all of a text’s substrings, and it directly answers questions such as counting distinct substrings.

Where It Is Used

Preprocessed text structures show up wherever the text is fixed and queries are numerous:

• Full-text indexing. Search over a document collection; scanning the text per query does not scale.
• Bioinformatics. Genetic sequences are long, the alphabet is small, and thousands of queries are made against the same sequence.
• Duplicate code and content detection. Through longest-common-piece queries.
• Compression. Finding repeated pieces; the Burrows–Wheeler transform rests directly on suffix sorting.

The common criterion is the same: once preprocessing cost is divided by the number of queries, does the gain remain? This question was asked for sublinear classes in the Reading Complexity Classes lesson; here its answer turns into a concrete choice of data structure.

Summary

• A suffix array is the starting positions that arrange all of a text’s suffixes in lexicographic order, and it takes up $n$ integers.
• Suffixes starting with a pattern occupy a contiguous range; binary search answers a query in $O(m \log n)$, and the occurrence count is given by the range’s width.
• The LCP array holds the common-prefix length of consecutive suffixes and is computed in $O(n)$; its largest value gives the longest repeated piece.
• The suffix tree arranges the same information as a tree; its query is $O(m)$, but its memory constant and implementation complexity are high.
• The choice of structure is decided by dividing preprocessing cost by the number of queries.

Next Step

The final question of text algorithms differs from search: storing the same information in less space. The next lesson builds the Huffman method, which produces variable-length codes based on character frequencies, and shows why a greedy choice yields the optimal code.