程序包 edu.princeton.cs.algs4

类 SuffixArray

java.lang.Object

edu.princeton.cs.algs4.SuffixArray

public class SuffixArray
extends java.lang.Object

The 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.

构造器概要

构造器

构造器	说明
SuffixArray(java.lang.String text)	Initializes a suffix array for the given text string.

方法概要

修饰符和类型	方法	说明
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(java.lang.String[] args)	Unit tests the SuffixArray data type.
int	rank(java.lang.String query)	Returns the number of suffixes strictly less than the query string.
java.lang.String	select(int i)	Returns the ith smallest suffix as a string.

从类继承的方法 java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

构造器详细资料

SuffixArray

public SuffixArray(java.lang.String text)

Initializes a suffix array for the given text string.

参数:

text - the input string

方法详细资料

length

public int length()

Returns the length of the input string.

返回:

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 ith smallest suffix.

参数:

i - an integer between 0 and n-1

返回:

the index into the original string of the ith smallest suffix

抛出:

java.lang.IllegalArgumentException - unless 0 <= i < n

lcp

public int lcp(int i)

Returns the length of the longest common prefix of the ith smallest suffix and the i-1st smallest suffix.

参数:

i - an integer between 1 and n-1

返回:

the length of the longest common prefix of the ith smallest suffix and the i-1st smallest suffix.

抛出:

java.lang.IllegalArgumentException - unless 1 <= i < n

select

public java.lang.String select(int i)

Returns the ith smallest suffix as a string.

参数:

i - the index

返回:

the i smallest suffix as a string

抛出:

java.lang.IllegalArgumentException - unless 0 <= i < n

rank

public int rank(java.lang.String query)

Returns the number of suffixes strictly less than the query string. We note that rank(select(i)) equals i for each i between 0 and n-1.

参数:

query - the query string

返回:

the number of suffixes strictly less than query

main

public static void main(java.lang.String[] args)

Unit tests the SuffixArray data type.

参数:

args - the command-line arguments