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 < npublic int lcp(int i)
i - an integer between 1 and n-1IllegalArgumentException - unless 1 <= i < npublic String select(int i)
i - the indexIllegalArgumentException - unless 0 <= i < npublic 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 stringquerypublic static void main(String[] args)
SuffixArray data type.args - the command-line arguments