- Free Articles
- Suffix Tree Construction in Hierarchical Memory Encyclopedia of Algorithms
- Probabilistic Data Forwarding in Wireless Sensor Networks Encyclopedia of Algorithms
- Renaming Encyclopedia of Algorithms
- Time in Philosophical Logic Encyclopedia of Database Systems
- Indoor Localization Encyclopedia of GIS
**More Free Articles**

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*) = *t*_{0}*t*_{1}⋅⋅⋅*t*_{n − 1}, i. e., a sequence of *n* *characters* from an *alphabet* Σ. For *i*∈[0,*n*], let *S* _{i} denote the *suffix* *T*[*i*,*n*) = *t*_{i}*t*_{i + 1}⋅⋅⋅*t*_{n − 1}. The output is the *suffix array* *S**A*[0,*n*] of *T*, a permutation of [0,*n*] satisfying *S*_{SA[0]} < *S*_{SA[1]} < ⋅⋅⋅ < *S*_{SA[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