Suffix Array Construction Algorithm

A suffix array is a sorted array of all the starting positions of every suffix of a string, and a suffix array construction algorithm builds this array efficiently rather than by the naive approach of generating and sorting every suffix directly, which is slow for long strings. Efficient construction methods use techniques such as prefix doubling, sorting suffixes by successively longer prefixes whose lengths double at each round, achieving O(n log n) time, while later linear-time methods such as the DC3 or skew algorithm achieve O(n) construction. Once built, a suffix array supports fast substring search and underlies many string processing structures, including full-text indexes and the Burrows-Wheeler transform.