Suffix Array

Sort all suffixes of a text once, and every later "does this pattern occur, and how often?" becomes a binary search. Suffix arrays sit behind full text indexes, genome tools and data compressors.

advanced⏱ 12 min read

←Builds on

2Merge Sort: Divide & ConquerSuffixes are sorted by doubling prefix lengths, an O(n log n) sorting job at heart.2Counting SortSorting rank pairs with counting sort keeps every doubling round linear.5Trie & AutocompleteA suffix array is the compact replacement for a trie of all suffixes.

Leads to→

This is where the roadmap ends. Look back at how far you came.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Sorted suffixes, stored as numbers

A string of length n has n suffixes. The suffix array SA lists their starting indices in lexicographic order of the suffixes. For banana:

SA = [5, 3, 1, 0, 4, 2], meaning a < ana < anana < banana < na < nana.

You never store the suffixes themselves, only n integers, so memory is O(n).

The key property: all suffixes that start with a pattern P sit next to each other in sorted order. Find the first and last of them with two binary searches, each comparing up to |P| characters per step. That is O(m log n) per query, and the size of the block is the number of occurrences.

02Building it fast: prefix doubling

Sorting the suffixes with ordinary string comparisons costs O(n² log n) in the worst case. The standard trick sorts by the first 1, then 2, then 4, 8, … characters.

After round k, every position has a rank: equal first k characters, equal rank. In the next round, the first 2k characters of suffix i are described by the pair (rank[i], rank[i + k]). Sorting pairs of small numbers is cheap, with no string comparisons at all.

After log n rounds all ranks are distinct and you are done. With a normal sort that is O(n log² n); with radix sort on the pairs, O(n log n). In the figure, banana is fully sorted after the round with 4 characters.

03Beyond search: the LCP array

Next to SA, people usually build the LCP array: lcp[i] is the length of the longest common prefix of the suffixes at SA[i − 1] and SA[i]. Kasai's algorithm computes it in O(n).

With SA and lcp you can answer questions that look hard:

number of distinct substrings: n(n+1)/2 − Σ lcp[i]
longest repeated substring: the maximum value in lcp
longest common substring of two strings: build SA on A + "#" + B

If you only need to search one pattern once, KMP or Z is simpler. The suffix array pays off when one text receives many queries, or when the question is about all substrings at once.

Cost at a glance

Build (prefix doubling + radix sort)O(n log n)

Search one patternO(m log n)

LCP array (Kasai)O(n)

MemoryO(n)

Remember

A suffix array is the list of suffix start positions in sorted order, so it takes only O(n) integers.
All occurrences of a pattern form one contiguous block in SA, found by binary search in O(m log n).
Prefix doubling sorts by 1, 2, 4, … characters using pairs of ranks, giving O(n log n) construction.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: At the end, notice that the matching suffixes form one block: the binary search only needs to find its edges.

Interactive visualizerfocus here, then space ← →

Suffix array: "banana" · Suffixes (unsorted)

0banana

1anana

2nana

3ana

4na

A suffix array is the sorted order of all suffixes of a string, stored as start indices. Powerful when you run many substring searches on one text.

Pseudocode

 1 list all suffixes with their start indices 2 sort the suffixes lexicographically → SA = their indices 3 search pattern P: binary search for the contiguous SA range starting with P 4 // SA stores only indices → O(n) memory

1 / 1

Check

Three questions. Pick an answer to see why.

What is the suffix array of "abab"?

In SA of "banana", the suffixes starting with "na" occupy rows 4 and 5. How many times does "na" occur?

In prefix doubling, how do you compare the first 2k characters of two suffixes?

Practice

Real problems to lock it in, easiest first.

CSESFinding Patterns intermediate↗CSESDistinct Substrings intermediate↗CSESRepeating Substring advanced↗LeetCodeLongest Duplicate Substring advanced↗