| | | 1 | | using MoreStructures.Utilities; |
| | | 2 | | |
| | | 3 | | namespace MoreStructures.SuffixArrays.Builders; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// An algorithm for building the <see cref="SuffixArray"/> directly from a <see cref="TextWithTerminator"/>, listing |
| | | 7 | | /// and sorting all suffixes of <see cref="Text"/>. |
| | | 8 | | /// </summary> |
| | | 9 | | /// <remarks> |
| | | 10 | | /// <para id="algo"> |
| | | 11 | | /// ALGORITHM |
| | | 12 | | /// <br/> |
| | | 13 | | /// The following steps are performed, lazily. |
| | | 14 | | /// <br/> |
| | | 15 | | /// - First all suffixes of the input <see cref="TextWithTerminator"/> are generated. |
| | | 16 | | /// <br/> |
| | | 17 | | /// - Then the suffixes are sorted in ascending order. |
| | | 18 | | /// <br/> |
| | | 19 | | /// - Finally, the 1st char of each suffix is taken. |
| | | 20 | | /// </para> |
| | | 21 | | /// <para id="complexity"> |
| | | 22 | | /// COMPLEXITY |
| | | 23 | | /// <br/> |
| | | 24 | | /// - There are n suffixes, where n is the length of the input text (including the terminator). |
| | | 25 | | /// <br/> |
| | | 26 | | /// - Sorting n strings requires n * log(n) comparisons, each comparing at most n chars. |
| | | 27 | | /// <br/> |
| | | 28 | | /// - Taking the first char of each of the suffixes takes O(1) time, and there are n of them. |
| | | 29 | | /// <br/> |
| | | 30 | | /// - Therefore, Time Complexity is O(n^2 * log(n)) and Space Complexity is O(n). |
| | | 31 | | /// </para> |
| | | 32 | | /// </remarks> |
| | | 33 | | public class NaiveSuffixArrayBuilder : ISuffixArrayBuilder |
| | | 34 | | { |
| | | 35 | | private readonly IComparer<string> Comparer; |
| | | 36 | | |
| | | 37 | | /// <summary> |
| | | 38 | | /// The <see cref="TextWithTerminator"/>, to build the <see cref="SuffixArray"/> of. |
| | | 39 | | /// </summary> |
| | 1860 | 40 | | public TextWithTerminator Text { get; } |
| | | 41 | | |
| | | 42 | | /// <summary> |
| | | 43 | | /// <inheritdoc cref="NaiveSuffixArrayBuilder" path="/summary"/> |
| | | 44 | | /// </summary> |
| | | 45 | | /// <param name="text"><inheritdoc cref="Text" path="/summary"/></param> |
| | 58 | 46 | | public NaiveSuffixArrayBuilder(TextWithTerminator text) |
| | 58 | 47 | | { |
| | 58 | 48 | | Text = text; |
| | 58 | 49 | | Comparer = StringIncludingTerminatorComparer.Build(text.Terminator); |
| | 58 | 50 | | } |
| | | 51 | | |
| | | 52 | | /// <summary> |
| | | 53 | | /// <inheritdoc cref="NaiveSuffixArrayBuilder" path="/summary"/> |
| | | 54 | | /// </summary> |
| | 58 | 55 | | public SuffixArray Build() => new(Enumerable |
| | 58 | 56 | | .Range(0, Text.Length) |
| | 901 | 57 | | .Select(i => string.Concat(Text[i..])) |
| | 901 | 58 | | .OrderBy(s => s, Comparer) |
| | 959 | 59 | | .Select(s => Text.Length - s.Length)); |
| | | 60 | | } |