Class NaiveSnssFinder

A ISnssFinder implementation which checks for the presence of each substring of the first text in the second text, from the longest to the shortest.

Inheritance
System.Object
NaiveSnssFinder
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.SuffixStructures.Matching
Assembly: MoreStructures.dll
Syntax
public class NaiveSnssFinder : ISnssFinder
Remarks

ADVANTAGES AND DISADVANTAGES
- Unlike SuffixStructureBasedSnssFinder derivations, this implementation doesn't require terminators, since it does not build any auxialiary structure.
- It also doesn't require additional space, except for iterations and index variables. So, it's a good solution for small input, when space is a hard constraint, much more than time.

ALGORITHM
- Lazily iterates over all substrings of text1, from the shortest (length 1) to the longest (length - 1).
- As soon as it finds one which is not contained in text2, it yield returns it.

COMPLEXITY
- Checking all substrings of text1 of variable length, from 1 to length - 1, is a quadratic with the length of text1. It doesn't require more than constant space (for iterators and index variables) when using string ranges (which are views of larger strings, optimized thanks to immutability.
- Each check of a substring of text1 in text2 takes O(sl) time, where sl is the length of the substring. Since the average length of the substring depends linearly on the length of text1 n, the check takes O(n).
- So overall Time Complexity is O(n^3) and Space Complexity is O(1).

Methods

| Improve this Doc View Source

Find(IEnumerable<Char>, IEnumerable<Char>)

Declaration
public IEnumerable<string> Find(IEnumerable<char> text1, IEnumerable<char> text2)
Parameters
Type Name Description
IEnumerable<System.Char> text1
IEnumerable<System.Char> text2
Returns
Type Description
IEnumerable<System.String>
Remarks

Implements

Extension Methods