Class NaiveBordersExtraction

An implementation of IBordersExtraction which checks every prefix of the text.

Inheritance
System.Object
NaiveBordersExtraction
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.Borders
Assembly: MoreStructures.dll
Syntax
public class NaiveBordersExtraction : IBordersExtraction
Remarks

ALGORITHM
- The algorithm checks all the prefixes of the text, which are not the text itself, by decreasing length.
- For each prefix, it checks whether the prefix is also a suffix of the text.
- If so, returns it.
- An empty string has no prefixes shorter than the text, so an empty sequence is returned.

COMPLEXITY
- A text T of length n has n - 1 prefixes which are strictly shorter than T.
- Each of the prefix has a length O(n).
- Checking whether a prefix of T of length w is also a suffix of T requires comparing all w chars.
- Therefore, Time Complexity is O(n^2) and Space Complexity is O(1).

Methods

| Improve this Doc View Source

GetAllBordersByDescLength(String)

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

Implements

Extension Methods