Class SuffixArrayX
 Object

 edu.princeton.cs.algs4.SuffixArrayX

public class SuffixArrayX extends Object
TheSuffixArrayX
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 character '\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 pathological 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 Summary
Constructors Constructor Description SuffixArrayX(String text)
Initializes a suffix array for the giventext
string.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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 theSuffixArrayX
data type.int
rank(String query)
Returns the number of suffixes strictly less than thequery
string.String
select(int i)
Returns the ith smallest suffix as a string.



Constructor Detail

SuffixArrayX
public SuffixArrayX(String text)
Initializes a suffix array for the giventext
string. Parameters:
text
 the input string


Method Detail

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

index
public int index(int i)
Returns the index into the original string of the ith smallest suffix. That is,text.substring(sa.index(i))
is the i smallest suffix. Parameters:
i
 an integer between 0 and n1 Returns:
 the index into the original string of the ith smallest suffix
 Throws:
IllegalArgumentException
 unless0 <=i < n

lcp
public int lcp(int i)
Returns the length of the longest common prefix of the ith smallest suffix and the i1st smallest suffix. Parameters:
i
 an integer between 1 and n1 Returns:
 the length of the longest common prefix of the ith smallest suffix and the i1st smallest suffix.
 Throws:
IllegalArgumentException
 unless1 <= i < n

select
public String select(int i)
Returns the ith smallest suffix as a string. Parameters:
i
 the index Returns:
 the i smallest suffix as a string
 Throws:
IllegalArgumentException
 unless0 <= i < n

rank
public int rank(String query)
Returns the number of suffixes strictly less than thequery
string. We note thatrank(select(i))
equalsi
for eachi
between 0 and n1. Parameters:
query
 the query string Returns:
 the number of suffixes strictly less than
query

main
public static void main(String[] args)
Unit tests theSuffixArrayX
data type. Parameters:
args
 the commandline arguments

