Suffix Array

A suffix array stores the starting positions of all suffixes of a string in sorted order.

It is a compact structure for answering questions about substrings and lexicographic order.

Core Idea

Every suffix starts at some index. Sorting those suffixes groups similar prefixes together. This makes repeated substring queries and longest-common-prefix reasoning possible.

A simple construction is easy to understand but can be too slow for large strings.

Function Contract

suffix_array(text) expects a string and returns the starting indexes of all suffixes in lexicographic order.

The simple implementation is meaning-first. It is not intended for large strings because it creates and compares many suffix slices.

Python Example

def suffix_array(text):
    return sorted(range(len(text)), key=lambda i: text[i:])

For learning, this shows the meaning directly: sort suffix starting indexes by the suffix text.

Step-by-Step Example

For "banana", suffixes include:

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

Sorted lexicographically, the suffix indexes are:

5, 3, 1, 0, 4, 2

because "a" comes before "ana", which comes before "anana", and so on.

Why It Helps

Sorted suffixes place similar prefixes near each other. That makes it possible to search for patterns with binary search and to reason about repeated substrings using neighboring suffixes.

Complexity

The simple Python implementation is not efficient for large strings because slicing creates suffix strings and sorting compares them. It is a meaning-first implementation.

Advanced suffix array construction can be much faster, but the concept starts with sorted suffix indexes.

Common Confusions

The suffix array stores indexes, not the suffix strings themselves.

The simple Python construction creates many slices and is not an efficient advanced implementation. It is a clarity-first version.

Another common mistake is confusing suffix arrays with tries. A suffix array sorts suffixes. A trie stores prefixes in a tree.

When To Use It

Use suffix array reasoning for many substring queries, lexicographic suffix order, repeated substrings, and problems where sorting all suffixes exposes useful structure.

Do not start with suffix arrays for simple one-off substring search. Simpler string matching is usually enough.

The Main Point

A suffix array sorts suffix starting positions so substring and lexicographic structure become searchable.