| | | 1 | | using MoreStructures.KnuthMorrisPratt.Borders; |
| | | 2 | | |
| | | 3 | | namespace MoreStructures.KnuthMorrisPratt.PrefixFunction; |
| | | 4 | | |
| | | 5 | | /// <inheritdoc cref="IPrefixFunctionCalculator" path="//*[not(self::summary or self::remarks)]"/> |
| | | 6 | | /// <summary> |
| | | 7 | | /// An implementation of <see cref="IPrefixFunctionCalculator"/> which retrieves the longest border, then checks its |
| | | 8 | | /// length. |
| | | 9 | | /// </summary> |
| | | 10 | | /// <remarks> |
| | | 11 | | /// <para id="algo"> |
| | | 12 | | /// ALGORITHM |
| | | 13 | | /// <br/> |
| | | 14 | | /// - The algorithm iterates over all the chars of the text, from the first to the last. |
| | | 15 | | /// <br/> |
| | | 16 | | /// - For each char at index i, it retrieves the longest border of the prefix, up to char at index i included, by |
| | | 17 | | /// using the <see cref="IBordersExtraction"/> implementation provided at construction time. |
| | | 18 | | /// <br/> |
| | | 19 | | /// - <see cref="IBordersExtraction.GetAllBordersByDescLength(string)"/> retrieves the borders from the longest to |
| | | 20 | | /// the shortest, whatever the implementation. Therefore, only the first border needs to be enumerated. |
| | | 21 | | /// <br/> |
| | | 22 | | /// - If no borders are found, the Prefix Function at index i is zero. Otherwise, it's the length of the longest. |
| | | 23 | | /// </para> |
| | | 24 | | /// <para id="complexity"> |
| | | 25 | | /// COMPLEXITY |
| | | 26 | | /// <br/> |
| | | 27 | | /// - There are as many prefixes of the text as chars. |
| | | 28 | | /// <br/> |
| | | 29 | | /// - The time and space cost of retrieving the longest border depends on the actual implementation of |
| | | 30 | | /// <see cref="IBordersExtraction"/> used, to retrieve the longest border, which, when it exists, it is the first |
| | | 31 | | /// in the sequence. |
| | | 32 | | /// <br/> |
| | | 33 | | /// - Checking whether a border has been found and, in case, its length are both constant time operations. |
| | | 34 | | /// <br/> |
| | | 35 | | /// - Therefore, Time Complexity is O(n * Tlb) and Space Complexity is O(n * Slb), where Tlb and Slb are the Time |
| | | 36 | | /// and Space Complexity of finding the longest border (1st item) via the provided |
| | | 37 | | /// <see cref="BordersExtraction"/>. |
| | | 38 | | /// <br/> |
| | | 39 | | /// - When <see cref="NaiveBordersExtraction"/> is used as <see cref="BordersExtraction"/>, Time Complexity is |
| | | 40 | | /// O(n^3) and Space Complexity is O(n). |
| | | 41 | | /// </para> |
| | | 42 | | /// </remarks> |
| | | 43 | | public class NaivePrefixFunctionCalculator : IPrefixFunctionCalculator |
| | | 44 | | { |
| | | 45 | | /// <summary> |
| | | 46 | | /// The <see cref="IBordersExtraction"/> implementation to be used, to retrieve the longest border of the text. |
| | | 47 | | /// </summary> |
| | 162 | 48 | | protected IBordersExtraction BordersExtraction { get; } |
| | | 49 | | |
| | | 50 | | /// <summary> |
| | | 51 | | /// <inheritdoc cref="NaivePrefixFunctionCalculator"/> |
| | | 52 | | /// </summary> |
| | | 53 | | /// <param name="bordersExtraction"><inheritdoc cref="BordersExtraction" path="/summary"/></param> |
| | 19 | 54 | | public NaivePrefixFunctionCalculator(IBordersExtraction bordersExtraction) |
| | 19 | 55 | | { |
| | 19 | 56 | | BordersExtraction = bordersExtraction; |
| | 19 | 57 | | } |
| | | 58 | | |
| | | 59 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 60 | | /// <remarks> |
| | | 61 | | /// <inheritdoc cref="NaivePrefixFunctionCalculator" path="/remarks"/> |
| | | 62 | | /// </remarks> |
| | | 63 | | public IEnumerable<int> GetValues(string text) => |
| | 26 | 64 | | from i in Enumerable.Range(0, text.Length) |
| | 162 | 65 | | let prefix = text[0..(i + 1)] |
| | 162 | 66 | | let longestBorderMaybe = BordersExtraction.GetAllBordersByDescLength(prefix).FirstOrDefault() |
| | 188 | 67 | | select longestBorderMaybe != null ? longestBorderMaybe.Length : 0; |
| | | 68 | | } |