The SuffixArrayX class represents a suffix array of a string of length N. It supports the Selecting the Ith smallest suffix, getting the Index of the Ith smallest suffix, computing the length of the Longest common prefix between the Ith smallest suffix and the I-1st smallest suffix, and determining the Rank of a query string (which is the number of suffixes strictly less than the query string).

This implementation uses 3-way radix quicksort to sort the array of suffixes. For a simpler (but less efficient) implementations of the same API, see . The Index and Length operations takes constant time in the worst case. The Lcp operation takes time proportional to the length of the longest common prefix. The Select operation takes time proportional to the length of the suffix and should be used primarily for debugging.

This implementation uses '\0' as a sentinel and assumes that the charater '\0' does not appear in the text.

In practice, this algorithm runs very fast. However, in the worst-case it can be very poor (e.g., a string consisting of N copies of the same character. We do not shuffle the array of suffixes before sorting because shuffling is relatively expensive and a pathologial input for which the suffixes start out in a bad order (e.g., sorted) is likely to be a bad input for this algorithm with or without the shuffle.