| | | 1 | | namespace MoreStructures.KnuthMorrisPratt.Borders; |
| | | 2 | | |
| | | 3 | | /// <inheritdoc cref="IBordersExtraction" path="//*[not(self::summary or self::remarks)]"/> |
| | | 4 | | /// <summary> |
| | | 5 | | /// An implementation of <see cref="IBordersExtraction"/> which checks every prefix of the text. |
| | | 6 | | /// </summary> |
| | | 7 | | /// <remarks> |
| | | 8 | | /// <para id="algo"> |
| | | 9 | | /// ALGORITHM |
| | | 10 | | /// <br/> |
| | | 11 | | /// - The algorithm checks all the prefixes of the text, which are not the text itself, by decreasing length. |
| | | 12 | | /// <br/> |
| | | 13 | | /// - For each prefix, it checks whether the prefix is also a suffix of the text. |
| | | 14 | | /// <br/> |
| | | 15 | | /// - If so, returns it. |
| | | 16 | | /// <br/> |
| | | 17 | | /// - An empty string has no prefixes shorter than the text, so an empty sequence is returned. |
| | | 18 | | /// </para> |
| | | 19 | | /// <para id="complexity"> |
| | | 20 | | /// COMPLEXITY |
| | | 21 | | /// <br/> |
| | | 22 | | /// - A text T of length n has n - 1 prefixes which are strictly shorter than T. |
| | | 23 | | /// <br/> |
| | | 24 | | /// - Each of the prefix has a length O(n). |
| | | 25 | | /// <br/> |
| | | 26 | | /// - Checking whether a prefix of T of length w is also a suffix of T requires comparing all w chars. |
| | | 27 | | /// <br/> |
| | | 28 | | /// - Therefore, Time Complexity is O(n^2) and Space Complexity is O(1). |
| | | 29 | | /// </para> |
| | | 30 | | /// </remarks> |
| | | 31 | | public class NaiveBordersExtraction : IBordersExtraction |
| | | 32 | | { |
| | | 33 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 34 | | /// <remarks> |
| | | 35 | | /// <inheritdoc cref="NaiveBordersExtraction" path="/remarks"/> |
| | | 36 | | /// </remarks> |
| | | 37 | | public IEnumerable<string> GetAllBordersByDescLength(string text) |
| | 171 | 38 | | { |
| | 171 | 39 | | var n = text.Length; |
| | | 40 | | |
| | 171 | 41 | | if (n == 0) |
| | 1 | 42 | | return Enumerable.Empty<string>(); |
| | | 43 | | |
| | 170 | 44 | | return |
| | 170 | 45 | | from i in Enumerable.Range(1, n - 1) |
| | 350 | 46 | | let prefix = text[0..(n - i)] |
| | 350 | 47 | | where prefix == text[i..] |
| | 286 | 48 | | select prefix; |
| | 171 | 49 | | } |
| | | 50 | | } |