Interface IPrefixFunctionCalculator

An algorithm which calculates the Prefix Function of the provided text.

Namespace: MoreStructures.KnuthMorrisPratt.PrefixFunction
Assembly: MoreStructures.dll
Syntax
public interface IPrefixFunctionCalculator
Remarks

The Prefix Function of a text T is a function s such that s(i) is the length of the longest border of the prefix of T up to the character with index i, included, i.e. T[0..(i+1)].
For example, if T = "aabaabacaabaa":
- s(0) = 0, since T[0..1] = "a" has no borders;
- s(1) = 1, since T[0..2] = "aa" has a single border "a", which is of length 1;
- s(2) = 0, since T[0..3] = "aab" has no borders;
- s(3) = 1, since T[0..4] = "aaba" has a single border "a", which is of length 1;
- s(4) = 1, since T[0..5] = "aabaa" has 2 borders { "a", "aa" }, and the longest one is of length 2;
- s(5) = 1, since T[0..6] = "aabaab" has 3 borders { "a", "aa", "aab" }, and the longest one of length 3;
- etc.

Methods

| Improve this Doc View Source

GetValues(String)

Calculate the values of the Prefix Function of the provided text.

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

The text, to calculate the Prefix Function of.
Returns
Type Description
IEnumerable<System.Int32>

The sequence of System.Int32 values of the Prefix Function.

Extension Methods