public class SuffixArray extends Object
SuffixArray
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 a nested class Suffix
to represent
a suffix of a string (using constant time and space) and
Arrays.sort()
to sort the array of suffixes.
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.
For alternate implementations of the same API, see
SuffixArrayX
, which is faster in practice (uses 3-way radix quicksort)
and uses less memory (does not create Suffix
objects)
and SuffixArrayJava6.java,
which relies on the constant-time substring extraction method that existed
in Java 6.
For additional documentation, see Section 6.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
SuffixArray(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 i-1st smallest suffix.
|
int |
length()
Returns the length of the input string.
|
static void |
main(String[] args)
Unit tests the
SuffixArray 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 SuffixArray(String text)
text
string.text
- the input stringpublic int length()
public int index(int i)
text.substring(sa.index(i))
is the ith smallest suffix.i
- an integer between 0 and n-1IllegalArgumentException
- unless 0 <= i < n
public int lcp(int i)
i
- an integer between 1 and n-1IllegalArgumentException
- 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 n-1.query
- the query stringquery
public static void main(String[] args)
SuffixArray
data type.args
- the command-line arguments