> > Suffix Array Construction: 2006; Kärkkäinen, Sanders, Burkhardt

This is the free portion of the full article. The full article is available to licensed users only.
How do I get access?

Suffix Array Construction

Keywords and Synonyms

Suffix sorting; Full-text index construction

Problem Definition

The suffix array [5,14] is the lexicographically sorted array of all the suffixes of a string. It is a popular text index structure with many applications. The subject of this entry are algorithms that construct the suffix array.

More precisely, the input to a suffix array construction algorithm is a text string T = T[0,n) = t0t1⋅⋅⋅tn − 1, i. e., a sequence of n characters from an alphabet Σ. For i∈[0,n], let S i denote the suffix T[i,n) = titi + 1⋅⋅⋅tn − 1. The output is the suffix array SA[0,n] of T, a permutation of [0,n] satisfying SSA[0] < SSA[1] < ⋅⋅⋅ < SSA[n], where < denotes the lexicographic order of strings.

Two specific models for the alphabet Σ are considered. An ordered alphabet is an arbitrary ordered set with constant time character comparisons. An integer alphabet is the integer range [1,n]. There is also a result that holds for any alphabet.

Many