data-structures string-algorithms
Definition
Suffix Array
A suffix array for a string
is an array of the starting positions of the suffixes of $T$$, sorted in lexicographic order. If
, then the -th sorted suffix starts at position .
Examples
Suffix array of
For
, append the fresh letter T’ = \text{banana}$$ in lexicographic order are: Their starting positions are:
Substring lookup
A pattern
occurs in at exactly those suffix-array positions whose suffixes have as a prefix. For
and , the matching suffixes are \text{anana}$ 3 1 \text{ana} 3 1 T$.