Class NaiveLcpArrayBuilder

An implementation of ILcpArrayBuilder which calculates the LCP Array using the definition.

Inheritance
System.Object
NaiveLcpArrayBuilder
KasaiLcpArrayBuilder
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.LongestCommonPrefix
Assembly: MoreStructures.dll
Syntax
public class NaiveLcpArrayBuilder : ILcpArrayBuilder
Remarks

ADVANTAGES AND DISADVANTAGES
- This implementation is the most straightforward, as the algorithm closely follows the definition.
- As such it is easy to implement and analyze, at the cost of worse Time and Space complexity than smarter implementations, using, for example, specific properties of subsequent LCP items of suffixes from the Suffix Array.
- The algorithm is also online. Therefore, values can be lazily computed.

ALGORITHM
- The implementation uses the externally provided SuffixArray, in combination with the Text.
- It iterates over the first n - 1 items of the SuffixArray SA, using LongestCommonPrefix(IEnumerable<Char>, IEnumerable<Char>) to calculate the length of the LCP between SA[i] and its successor, SA[i + 1].
- That represents the i-th element of the LCP Array.

COMPLEXITY
- The SuffixArray is externally provided, so it's building cost is not included in this analysis.
- The algorithm runs n - 1 iterations, each one building two strings (the prefix starting at SA[i] and the one starting at SA[i + 1]), then comparing them char by char, to find the LCP.
- Prefixes have in general O(n) length, and LongestCommonPrefix(IEnumerable<Char>, IEnumerable<Char>) has Time Complexity linear in the input, and constant Space Complexity.
- Therefore, Time Complexity is O(n^2) and Space Complexity is O(n).

Constructors

| Improve this Doc View Source

NaiveLcpArrayBuilder(TextWithTerminator, SuffixArray)

Declaration
public NaiveLcpArrayBuilder(TextWithTerminator text, SuffixArray suffixArray)
Parameters
Type Name Description
TextWithTerminator text

MoreStructures.SuffixArrays.SuffixArray suffixArray

Remarks

Properties

| Improve this Doc View Source

SuffixArray

The Suffix Array of the Text, required to calculate the MoreStructures.SuffixArrays.LongestCommonPrefix.LcpArray.

Declaration
public SuffixArray SuffixArray { get; }
Property Value
Type Description
MoreStructures.SuffixArrays.SuffixArray
| Improve this Doc View Source

Text

The terminator-terminated string, to calculate the MoreStructures.SuffixArrays.LongestCommonPrefix.LcpArray of.

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

Methods

| Improve this Doc View Source

Build()

Declaration
public virtual LcpArray Build()
Returns
Type Description
MoreStructures.SuffixArrays.LongestCommonPrefix.LcpArray
Remarks

Implements

Extension Methods