| | | 1 | | using MoreStructures.Utilities; |
| | | 2 | | |
| | | 3 | | namespace MoreStructures.SuffixStructures.Matching; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// A <see cref="ISnssFinder"/> implementation which checks for the presence of each substring of the first text in the |
| | | 7 | | /// second text, from the longest to the shortest. |
| | | 8 | | /// </summary> |
| | | 9 | | /// <remarks> |
| | | 10 | | /// <para id="advantages"> |
| | | 11 | | /// ADVANTAGES AND DISADVANTAGES |
| | | 12 | | /// <br/> |
| | | 13 | | /// - Unlike <see cref="SuffixStructureBasedSnssFinder"/> derivations, this implementation doesn't require |
| | | 14 | | /// terminators, since it does not build any auxialiary structure. |
| | | 15 | | /// <br/> |
| | | 16 | | /// - It also doesn't require additional space, except for iterations and index variables. So, it's a good |
| | | 17 | | /// solution for small input, when space is a hard constraint, much more than time. |
| | | 18 | | /// </para> |
| | | 19 | | /// <para id="algo"> |
| | | 20 | | /// ALGORITHM |
| | | 21 | | /// <br/> |
| | | 22 | | /// - Lazily iterates over all substrings of text1, from the shortest (length 1) to the longest (length - 1). |
| | | 23 | | /// <br/> |
| | | 24 | | /// - As soon as it finds one which is not contained in text2, it yield returns it. |
| | | 25 | | /// </para> |
| | | 26 | | /// <para id="complexity"> |
| | | 27 | | /// COMPLEXITY |
| | | 28 | | /// <br/> |
| | | 29 | | /// - Checking all substrings of text1 of variable length, from 1 to length - 1, is a quadratic with the length of |
| | | 30 | | /// text1. It doesn't require more than constant space (for iterators and index variables) when using string |
| | | 31 | | /// ranges (which are views of larger strings, optimized thanks to immutability. |
| | | 32 | | /// <br/> |
| | | 33 | | /// - Each check of a substring of text1 in text2 takes O(sl) time, where sl is the length of the substring. Since |
| | | 34 | | /// the average length of the substring depends linearly on the length of text1 n, the check takes O(n). |
| | | 35 | | /// <br/> |
| | | 36 | | /// - So overall Time Complexity is O(n^3) and Space Complexity is O(1). |
| | | 37 | | /// </para> |
| | | 38 | | /// </remarks> |
| | | 39 | | public class NaiveSnssFinder : ISnssFinder |
| | | 40 | | { |
| | | 41 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 42 | | /// <remarks> |
| | | 43 | | /// <inheritdoc cref="NaiveSnssFinder" path="/remarks"/> |
| | | 44 | | /// </remarks> |
| | | 45 | | public IEnumerable<string> Find(IEnumerable<char> text1, IEnumerable<char> text2) |
| | 14 | 46 | | { |
| | 14 | 47 | | var string1 = string.Concat(text1); |
| | 14 | 48 | | var string2 = string.Concat(text2); |
| | | 49 | | |
| | 14 | 50 | | if (string2.Contains(string1)) |
| | 3 | 51 | | return Enumerable.Empty<string>(); |
| | | 52 | | |
| | 11 | 53 | | var results = |
| | 11 | 54 | | from length in Enumerable.Range(1, string1.Length) // All substrings of non-zero length |
| | 317 | 55 | | from start in Enumerable.Range(0, string1.Length - length + 1) |
| | 231 | 56 | | let substringOfString1 = string1[start..(start + length)] |
| | 231 | 57 | | where !string2.Contains(substringOfString1) |
| | 66 | 58 | | select substringOfString1; |
| | | 59 | | |
| | 11 | 60 | | var (firstOrEmpty, _) = results.EnumerateAtMostFirst(1); |
| | 11 | 61 | | var first = firstOrEmpty.Single(); |
| | 55 | 62 | | return results.TakeWhile(s => s.Length == first.Length).Prepend(first); |
| | 14 | 63 | | } |
| | | 64 | | } |