Suffix Arrays Introduction

Why Index Every Suffix

If you sort all suffixes of a string, substrings start to behave like prefixes of those sorted suffixes. That observation is the heart of suffix arrays. Instead of storing an enormous suffix trie or tree, a suffix array stores only the starting indices of suffixes in lexicographic order. The array is compact, but the order it captures is powerful.

Why is that useful? Suppose you want to know whether nan appears in banana. If all suffixes are sorted, every suffix beginning with n sits in one contiguous neighborhood. That means binary search becomes possible. Or suppose you want the longest repeated substring. Adjacent suffixes in sorted order share the most promising common prefixes, so repetition questions turn into longest-common-prefix questions between neighbors.

Building a Suffix Array Naively

The easiest construction is conceptually simple. Generate every suffix s[i:], pair it with its start index i, sort those pairs lexicographically by the suffix string, and then keep only the sorted indices. This is not the fastest known construction, but it is the right first version because it makes the structure concrete.

The naive cost is often described as O(n^2 log n). There are n suffixes, sorting costs O(n log n) comparisons, and a comparison between two suffix strings can inspect many characters. Later, more advanced algorithms such as prefix-doubling methods reduce construction to O(n log n), and linear-time algorithms like SA-IS exist too, but the conceptual lesson does not require them yet.

Banana Worked Example

The classic teaching string is banana because its repeated ana pattern makes the value of sorted suffixes obvious. First list every suffix with its starting index, then sort them lexicographically.

0 -> banana
1 -> anana
2 -> nana
3 -> ana
4 -> na
5 -> a

Sorted suffixes:
5 -> a
3 -> ana
1 -> anana
0 -> banana
4 -> na
2 -> nana

Suffix array = [5, 3, 1, 0, 4, 2]

Now add one more useful array mentally: the longest common prefix between neighboring sorted suffixes. Between a and ana, the common prefix length is 1. Between ana and anana, it is 3. Between na and nana, it is 2. The maximum neighbor LCP is therefore 3, which tells us the longest repeated substring is ana.

suffixes:   a   ana   anana   banana   na   nana
LCP with previous: -   1     3       0        0    2

maximum LCP = 3 => longest repeated substring is 'ana'

Searching and Repetition Queries

Substring search on a suffix array works by binary searching over sorted suffixes. To ask whether nan appears in banana, compare nan to the middle suffix, move left or right lexicographically, and stop when some suffix begins with the query. Because the suffixes are sorted, matching prefixes occupy a contiguous range, just like words with the same starting letters in a dictionary.

That same sorted view helps with more than membership. Longest repeated substring comes from large LCP values. Counting distinct substrings can be derived from total suffix lengths minus shared prefixes. Faster construction algorithms matter when n is huge, but the problem-solving intuition already appears in the naive version: suffix order reveals repeated structure.

Go Implementation

This implementation constructs a suffix array naively because the goal of this lesson is clarity. It then uses binary search over the sorted suffix starts to answer substring-membership queries. The helper comparator uses the original string plus a start index; no duplicated suffix storage is required after sorting the indices.

Practice Problems

Quiz

Summary

• A suffix array is a sorted list of suffix starting indices, not a copied list of suffix strings.
• The naive build is easy to understand and already reveals why the structure is useful for search and repetition tasks.
• Binary search over sorted suffixes supports substring queries, while adjacent common prefixes expose repeated substrings.
• Neighbor LCP values are the bridge from suffix order to longest-duplicate and distinct-substring problems.
• Advanced construction algorithms exist, but the naive version is the right conceptual entry point for this module.