Class NaivePrefixFunctionCalculator

An implementation of IPrefixFunctionCalculator which retrieves the longest border, then checks its length.

Inheritance
System.Object
NaivePrefixFunctionCalculator
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.KnuthMorrisPratt.PrefixFunction
Assembly: MoreStructures.dll
Syntax
public class NaivePrefixFunctionCalculator : IPrefixFunctionCalculator
Remarks

ALGORITHM
- The algorithm iterates over all the chars of the text, from the first to the last.
- For each char at index i, it retrieves the longest border of the prefix, up to char at index i included, by using the IBordersExtraction implementation provided at construction time.
- GetAllBordersByDescLength(String) retrieves the borders from the longest to the shortest, whatever the implementation. Therefore, only the first border needs to be enumerated.
- If no borders are found, the Prefix Function at index i is zero. Otherwise, it's the length of the longest.

COMPLEXITY
- There are as many prefixes of the text as chars.
- The time and space cost of retrieving the longest border depends on the actual implementation of IBordersExtraction used, to retrieve the longest border, which, when it exists, it is the first in the sequence.
- Checking whether a border has been found and, in case, its length are both constant time operations.
- Therefore, Time Complexity is O(n * Tlb) and Space Complexity is O(n * Slb), where Tlb and Slb are the Time and Space Complexity of finding the longest border (1st item) via the provided BordersExtraction.
- When NaiveBordersExtraction is used as BordersExtraction, Time Complexity is O(n^3) and Space Complexity is O(n).

Constructors

| Improve this Doc View Source

NaivePrefixFunctionCalculator(IBordersExtraction)

Declaration
public NaivePrefixFunctionCalculator(IBordersExtraction bordersExtraction)
Parameters
Type Name Description
IBordersExtraction bordersExtraction

Properties

| Improve this Doc View Source

BordersExtraction

The IBordersExtraction implementation to be used, to retrieve the longest border of the text.

Declaration
protected IBordersExtraction BordersExtraction { get; }
Property Value
Type Description
IBordersExtraction

Methods

| Improve this Doc View Source

GetValues(String)

Declaration
public IEnumerable<int> GetValues(string text)
Parameters
Type Name Description
System.String text
Returns
Type Description
IEnumerable<System.Int32>
Remarks

Implements

Extension Methods