public class SuffixArrayX extends Object
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 i1st 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 3way radix quicksort to sort the array of suffixes.
For a simpler (but less efficient) implementations of the same API, see
SuffixArray
.
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 worstcase 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.
For additional documentation, see Section 6.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description 

SuffixArrayX(String text)
Initializes a suffix array for the given
text string. 
Modifier and Type  Method and Description 

int 
index(int i)
Returns the index into the original string of the ith smallest suffix.

int 
lcp(int i)
Returns the length of the longest common prefix of the ith
smallest suffix and the i1st smallest suffix.

int 
length()
Returns the length of the input string.

static void 
main(String[] args)
Unit tests the
SuffixArrayx data type. 
int 
rank(String query)
Returns the number of suffixes strictly less than the
query string. 
String 
select(int i)
Returns the ith smallest suffix as a string.

public SuffixArrayX(String text)
text
string.text
 the input stringpublic int length()
public int index(int i)
text.substring(sa.index(i))
is the i smallest suffix.i
 an integer between 0 and n1IllegalArgumentException
 unless 0 <=i < n
public int lcp(int i)
i
 an integer between 1 and n1IllegalArgumentException
 unless 1 <= i < n
public String select(int i)
i
 the indexIllegalArgumentException
 unless 0 <= i < n
public int rank(String query)
query
string.
We note that rank(select(i))
equals i
for each i
between 0 and n1.query
 the query stringquery
public static void main(String[] args)
SuffixArrayx
data type.args
 the commandline arguments