Click or drag to resize
SuffixArray Class

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 Array.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 , which is faster in practice (uses 3-way radix quicksort) and uses less memory (does not create Suffix objects)

Inheritance Hierarchy
SystemObject
  Algs4NetSuffixArray

Namespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
Syntax
C#
Copy
public class SuffixArray

The SuffixArray type exposes the following members.

Constructors
  NameDescription
Public methodSuffixArray
Initializes a suffix array for the given text string.
Top
Properties
  NameDescription
Public propertyLength
Returns the length of the input string.
Top
Methods
  NameDescription
Public methodIndex
Returns the index into the original string of the ith smallest suffix. That is, text.Substring(sa.Index(i)) is the ith smallest suffix.
Public methodLcp
Returns the length of the longest common prefix of the Ith smallest suffix and the i-1st smallest suffix.
Public methodStatic memberMainTest
Demo test the SuffixArray data type.
Public methodRank
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.
Public methodSelect
Returns the ith smallest suffix as a string.
Top
Remarks

For additional documentation, see Section 6.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

This class is a C# port from the original Java class SuffixArray implementation by the respective authors.

See Also