Class NaivePartiallyRecursiveSuffixTrieBuilder

Builds objects, such as edges and nodes, for SuffixTrieNode structures.

Inheritance
System.Object
NaivePartiallyRecursiveSuffixTrieBuilder
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.SuffixTries.Builders
Assembly: MoreStructures.dll
Syntax
public class NaivePartiallyRecursiveSuffixTrieBuilder : IBuilder<SuffixTrieEdge, SuffixTrieNode>
Remarks

ALGORITHM
Implemented iteratively, with one level of recursion per char of each suffix of the input TextWithTerminator (where the longest suffix is the text itself).

ADVANTAGES AND DISADVANTAGES
Limited by call stack depth and usable with input text of a "reasonable" length (i.e. string having a length < ~1K chars).

COMPLEXITY
- Time Complexity = O(t^2 * as) and Space Complexity = O(t^2) where t = length of the text to match and as = size of the alphabet of the text.
- If the alphabet is of constant size, complexity is quadratic.

Methods

| Improve this Doc View Source

BuildTree(TextWithTerminator[])

Declaration
public SuffixTrieNode BuildTree(params TextWithTerminator[] texts)
Parameters
Type Name Description
TextWithTerminator[] texts
Returns
Type Description
SuffixTrieNode
Remarks

Implements

Extension Methods