---
title: 'Suffix Arrays and Trees'
source: 'https://academia.sh/en/courses/algorithms/suffix-arrays-and-trees'
course: Algorithms
language: en
updated: '2026-08-17T18:07:49+00:00'
license: 'CC BY-SA 4.0'
---

# Suffix Arrays and Trees

Structures that preprocess text, building a suffix array and querying it with binary search, the LCP array, comparison with the suffix tree, and applications.

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**.

```python
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.

```python
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)$.

```python
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.

```python
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.