Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 225 ยท Strings

Suffix Arrays and Suffix Trees

Build a suffix array by sorting, speed it up with prefix doubling, compute the LCP array with Kasai, and solve substring problems. Suffix trees explained.

Pattern-matching algorithms such as KMP and Z preprocess the pattern and then scan the text. That is perfect for one search. But what if the text stays the same and you will ask thousands of questions about it: "does ana occur?", "what is the longest repeated substring?", "how many distinct substrings are there?" Then it pays to preprocess the text once.

The classic answer is to index every suffix of the text. Every substring is a prefix of some suffix, so a sorted list of suffixes turns substring questions into prefix questions, which binary search handles easily. A suffix array stores that sorted list compactly; a suffix tree stores the suffixes as a tree. In this lesson you build a suffix array by simple sorting, make it faster, add the LCP array, and use both to solve several problems.

Suffixes of a string

The suffixes of banana are all the tails of the string:

TEXT
index  suffix
  0    banana
  1    anana
  2    nana
  3    ana
  4    na
  5    a

A suffix array sa lists the starting indexes of these suffixes in sorted (dictionary) order:

TEXT
sorted suffixes     sa
a                   5
ana                 3
anana               1
banana              0
na                  4
nana                2

sa = [5, 3, 1, 0, 4, 2]

Storing only indexes costs O(n) memory, though the suffixes themselves would take O(nยฒ) characters in total.

Building a suffix array by sorting

The simplest way: sort the indexes by the suffix they start. It takes only one line of Python.

Python Suffix array by sorting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

How fast is it? Sorting does O(n log n) comparisons, and each comparison of two suffixes can take O(n) characters, so the worst case is O(nยฒ log n). The slicing s[i:] also copies up to n characters per key, so memory use is O(nยฒ) at its peak. That is fine for strings of a few thousand characters, and impossible for a genome with a billion.

Faster: prefix doubling

The idea behind prefix doubling is to sort suffixes by their first 1 character, then by their first 2, then 4, then 8, and so on. Sorting by the first 2k characters uses the ranks from the previous round: a suffix's key is the pair (rank of its first k characters, rank of the next k characters). After about log n rounds the first 2k characters cover the whole string, so the order is final. Each round sorts n items in O(n log n), giving O(n logยฒ n) overall.

Python Prefix doubling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For "aaaaaaaa" the loop needs more rounds than for "banana": highly repetitive strings are the hard case, because many suffixes share long prefixes. Optimal algorithms such as SA-IS build the array in O(n), but they are much more intricate; know that they exist.

Many programs append a sentinel character such as $ that is smaller than every other character. It guarantees that no suffix is a prefix of another, which simplifies the theory. With the plain sort above, a shorter suffix automatically sorts before a longer one that starts with it (a before ana), so we can skip the sentinel.

Searching with a suffix array

All occurrences of pattern are suffixes that start with pattern, and those sit next to each other in the sorted list. Two binary searches find the block: O(m log n) time for a pattern of length m (each comparison looks at up to m characters).

Python Find a pattern with binary search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

bisect accepts a key= argument (Python 3.10+) that is applied to the array elements, not to the searched value, which is exactly what we need.

The LCP array

Neighboring suffixes in sorted order tend to share long prefixes. The LCP array (longest common prefix) records this: lcp[i] is the length of the common prefix of sa[i] and sa[i-1] (with lcp[0] = 0).

TEXT
sa   suffix      lcp
5    a            0
3    ana          1   (a)
1    anana        3   (ana)
0    banana       0
4    na           0
2    nana         2   (na)

Computing each LCP from scratch costs O(n) per pair. Kasai's algorithm does it in O(n) overall with one observation: if suffix i shares k characters with the suffix before it in sorted order, then suffix i + 1 shares at least k - 1 characters with its predecessor. Process suffixes in text order (i = 0, 1, 2, ...) and reuse k - 1 instead of starting again from 0. The pointer k rises by at most n in total and falls by at most 1 per step, so the whole loop is linear.

Python Kasai's LCP algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

What a suffix array plus LCP can do

Longest repeated substring. A substring that occurs twice is a common prefix of two suffixes, and the longest such prefixes are between neighbors in sorted order. So the answer is simply max(lcp), and the substring is the first max(lcp) characters of the corresponding suffix. With the rolling-hash binary search the answer is probabilistic; here it is exact.

Number of distinct substrings. Every distinct substring is a prefix of at least one suffix. A suffix of length L has L prefixes, but the first lcp of them were already counted for the previous suffix in sorted order. So

TEXT
distinct = sum over suffixes of (length of suffix) - sum(lcp)
         = n(n + 1) / 2 - sum(lcp)

Longest common substring of two strings. Join them as a + "#" + b, build the array, and look for adjacent suffixes coming from different strings with a large LCP.

Python Repeated and distinct substrings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute-force column builds a set of all substrings, which takes O(nยณ) time and memory; the suffix-array version agrees and needs only sorting plus a linear scan.

Suffix trees

A suffix tree is a compressed trie of all suffixes of the string (with a terminal $). Each root-to-leaf path spells one suffix; chains of single-child nodes are merged into one edge labeled with a substring, which stores two indexes instead of characters.

TEXT
suffix tree for "banana$" (edge labels)

root
 |- "$"                    (suffix 6: the empty suffix)
 |- "banana$"             (suffix 0)
 |- "a"
 |    |- "$"              (suffix 5: the single "a")
 |    |- "na"
 |         |- "$"         (suffix 3: "ana")
 |         |- "na$"       (suffix 1: "anana")
 |- "na"
      |- "$"              (suffix 4: "na")
      |- "na$"            (suffix 2: "nana")

A suffix tree for a string of length n has O(n) nodes and answers "is p a substring?" in O(m), independent of n. Ukkonen's algorithm builds it in O(n). The simple way to see the structure is to build a plain (uncompressed) trie of all suffixes in O(nยฒ) and then merge the chains:

Python A suffix trie and its compressed form

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The uncompressed trie shown here needs O(nยฒ) nodes in the worst case; real suffix trees avoid that with edge labels as index ranges.

Generalized suffix trees and many strings

Everything so far indexed one string. A generalized suffix tree indexes several strings at once: it is a single compressed trie holding every suffix of every string, where each leaf records which string (and which position) it came from. It answers questions such as "which of my documents contain this pattern?" in O(m) for a pattern of length m, and "what is the longest substring shared by all of the strings?".

Building one is easy to explain: join the strings with a separator that is unique to each boundary, s1 + "#1" + s2 + "#2" + ..., and build the suffix tree (or the suffix array plus LCP) of the joined text. The separators must appear nowhere else and must all differ from each other. Then no common prefix of two suffixes can run across a separator, because two different suffixes never reach the same separator at the same offset, so every match found lies inside the individual strings. A suffix's owner string is found by a binary search on the separator positions.

Longest common substring of k strings

The longest substring present in all k strings is the deepest point in the generalized tree whose subtree has leaves from every string. On a suffix array this becomes a sliding window: sort all the suffixes, label each suffix with its string, and find windows of consecutive suffixes that contain all k labels. Inside a window the shared prefix length is the minimum LCP across it, and the answer is the best such minimum over all windows.

Python Longest substring common to k strings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first answer, ograph, appears in all three words (phot-ograph, tom-ograph-y, mon-ograph). The second answer is cde, and two strings with nothing in common give the empty string. The code was also checked against a brute-force search on 1,500 random small strings.

Counting documents for a pattern

The same index answers "in how many of the strings does p appear?" Binary search the suffix array for the block of suffixes that start with p, then count the distinct owners in that block. With a table of "previous suffix of the same string" and a range-counting structure such as a Fenwick tree, this drops to O(m + log n) per query, which is the idea behind document-retrieval indexes.

Suffix array or suffix tree?

Suffix array (+ LCP) Suffix tree
Space O(n) integers O(n) nodes, big constants
Pattern search O(m log n) O(m)
Easy to code yes no (Ukkonen is tricky)
Used in practice very common bioinformatics, text indexes
Key tool LCP array suffix links

With an LCP array and a range-minimum structure such as a sparse table, a suffix array can match a suffix tree on most queries while being much simpler and smaller. That is why competitive programmers rarely write suffix trees.

Common mistakes

  • Sorting full slices on large strings. sorted(range(n), key=lambda i: s[i:]) copies suffixes and is quadratic in memory; use prefix doubling for big inputs.
  • Confusing lcp[i] with the neighbour on the right. In this lesson lcp[i] compares sa[i] with sa[i-1]. Other texts shift the index; always check the convention.
  • Forgetting that two different strings need a separator when concatenated, so that a match cannot straddle the boundary.
  • Counting distinct substrings with a set for long strings, which is O(nยณ).
  • Using the suffix array for a single search. For one pattern in one text, KMP is simpler and faster to set up.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the suffix array of a string contain?

    sa[i] is the start position of the i-th smallest suffix in dictionary order.
  2. 2. What is the suffix array of 'banana'?

    The sorted suffixes are a, ana, anana, banana, na, nana, which start at 5, 3, 1, 0, 4 and 2.
  3. 3. Why is the longest repeated substring found with max(lcp)?

    Two suffixes that share a long prefix sort close together, so the best pair is always adjacent in the array.
  4. 4. How many distinct substrings does a string of length n have, given its LCP array?

    Each suffix of length L contributes L prefixes, of which lcp were already contributed by its predecessor in the sorted order.
  5. 5. What is the key observation behind Kasai's O(n) LCP algorithm?

    Dropping the first character of both suffixes keeps k - 1 characters in common, so the comparison never restarts from zero.

Summary

  • Every substring is a prefix of some suffix, so indexing the suffixes indexes all substrings.
  • The suffix array lists suffix start positions in sorted order; sorting builds it in O(nยฒ log n) worst case, prefix doubling in O(n logยฒ n), and SA-IS in O(n).
  • Pattern search is two binary searches: O(m log n).
  • The LCP array (Kasai, O(n)) gives longest repeated substring, the count of distinct substrings and longest common substring.
  • A suffix tree is a compressed trie of all suffixes with O(m) search; it is powerful but harder to build than a suffix array.

Next: Linked Lists, a new section on structures built from nodes and pointers instead of contiguous memory.