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