Suffix array ($\mathrm{SA}$)

A suffix array stores starting positions of a string's suffixes in lexicographic order. All suffixes starting with a fixed query occupy a consecutive interval. This permits string-searching algorithms to search a compact list of positions instead of storing every suffix explicitly.