tag

#sa-is

2 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

SA IS

SA IS SA IS is a linear-time suffix array construction algorithm. It sorts a carefully chosen subset of suffixes, called LMS suffixes, then induces the order of all remaining suffixes from them. It is one of the standard practical algorithms for building suffix arrays in linear time. Problem Given a string $S$ of length $n$, construct its suffix array: $$ SA = \text{sorted indices of all suffixes of } S...

Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

SA-IS Suffix Array

SA-IS Suffix Array Construction SA-IS constructs a suffix array in linear time by classifying characters and recursively sorting a reduced problem of LMS substrings. It is one of the most efficient practical algorithms for suffix array construction. Problem Given a string $T$ of length $n$, construct its suffix array: $$ SA[0 \dots n-1] $$ such that suffixes of $T$ are in lexicographic order. Key Idea Each position in the string...