Class NaiveSuffixArrayBuilder

An algorithm for building the MoreStructures.SuffixArrays.SuffixArray directly from a TextWithTerminator, listing and sorting all suffixes of Text.

Inheritance
System.Object
NaiveSuffixArrayBuilder
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.SuffixArrays.Builders
Assembly: MoreStructures.dll
Syntax
public class NaiveSuffixArrayBuilder : ISuffixArrayBuilder
Remarks

ALGORITHM
The following steps are performed, lazily.
- First all suffixes of the input TextWithTerminator are generated.
- Then the suffixes are sorted in ascending order.
- Finally, the 1st char of each suffix is taken.

COMPLEXITY
- There are n suffixes, where n is the length of the input text (including the terminator).
- Sorting n strings requires n * log(n) comparisons, each comparing at most n chars.
- Taking the first char of each of the suffixes takes O(1) time, and there are n of them.
- Therefore, Time Complexity is O(n^2 * log(n)) and Space Complexity is O(n).

Constructors

| Improve this Doc View Source

NaiveSuffixArrayBuilder(TextWithTerminator)

Declaration
public NaiveSuffixArrayBuilder(TextWithTerminator text)
Parameters
Type Name Description
TextWithTerminator text

Properties

| Improve this Doc View Source

Text

The TextWithTerminator, to build the MoreStructures.SuffixArrays.SuffixArray of.

Declaration
public TextWithTerminator Text { get; }
Property Value
Type Description
TextWithTerminator

Methods

| Improve this Doc View Source

Build()

Declaration
public SuffixArray Build()
Returns
Type Description
MoreStructures.SuffixArrays.SuffixArray

Implements

Extension Methods