| | | 1 | | using MoreStructures.SuffixTrees; |
| | | 2 | | |
| | | 3 | | namespace MoreStructures.SuffixArrays; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// A Partial <see cref="SuffixArray"/> which only contains the indexes of the Suffix Array which are multiple of a |
| | | 7 | | /// given constant <see cref="K"/> (0, k, 2k, ...), indexed by their position in the complete Suffix Array. |
| | | 8 | | /// </summary> |
| | | 9 | | /// <param name="K"> |
| | | 10 | | /// The constant, whose multiples (0, k, 2k, ...) are the indexes of the Suffix Array stored in |
| | | 11 | | /// <paramref name="Indexes"/>. A <see cref="SuffixArray"/> corresponds to a <see cref="IndexModKPartialSuffixArray"/> |
| | | 12 | | /// with <paramref name="K"/> equal to 1. |
| | | 13 | | /// </param> |
| | | 14 | | /// <param name="Indexes">The indexes multiple of <paramref name="K"/>.</param> |
| | | 15 | | /// <remarks> |
| | | 16 | | /// <see cref="SuffixArray"/> is a space-efficient alternative to <see cref="SuffixTreeNode"/> structures, due to |
| | | 17 | | /// their Θ(n) with c=1 space used, when the size of an index can be considered constant w.r.t. the size of the input |
| | | 18 | | /// strings. |
| | | 19 | | /// <br/> |
| | | 20 | | /// There are, however, cases where even the linear Space Complexity of a <see cref="SuffixArray"/> is considered still |
| | | 21 | | /// too high, and a smaller data structure has to be stored, potentially at the cost of the algorithm runtime. |
| | | 22 | | /// <br/> |
| | | 23 | | /// These are the scenarios where a Partial Suffix Array is used. |
| | | 24 | | /// <br/> |
| | | 25 | | /// Text pattern matching with Suffix Arrays can also be done with partial structures, for example by using the |
| | | 26 | | /// Last-First property of the Burrows-Wheeler Transform and its sorted version. |
| | | 27 | | /// </remarks> |
| | 3 | 28 | | public record struct IndexModKPartialSuffixArray(int K, IDictionary<int, int> Indexes); |