| | | 1 | | namespace MoreStructures.SuffixArrays.LongestCommonPrefix; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// The LCP Array of a string S of length n is defined as an array LCP of length n - 1 such that LCP[i] is the |
| | | 5 | | /// length of the prefix in common between the suffixes starting at SA[i] and SA[i + 1], where SA is the Suffix |
| | | 6 | | /// Array of S, for each i from 0 to n - 1 excluded. |
| | | 7 | | /// </summary> |
| | | 8 | | /// <remarks> |
| | | 9 | | /// The LCP Array of a string of length n has n - 1 items. |
| | | 10 | | /// </remarks> |
| | | 11 | | /// <example> |
| | | 12 | | /// Given the string <c>S = "mississippi$"</c> with terminator char <c>'$'</c>, S has Suffix Array |
| | | 13 | | /// <c>SA = { 11, 10, 7, 4, ... }</c>. |
| | | 14 | | /// <br/> |
| | | 15 | | /// - The 1-st item of the LCP Array of S is the length of the prefix in common between the suffix starting at |
| | | 16 | | /// SA[0], <c>"$"</c>, and the one starting at SA[1], <c>"i$"</c>. Such prefix is the empty string, therefore |
| | | 17 | | /// <c>LCP[0] = 0</c>. |
| | | 18 | | /// <br/> |
| | | 19 | | /// - The 2-nd item of the LCP Array of S is the length of the prefix in common between the suffix starting at |
| | | 20 | | /// SA[1], <c>"i$"</c>, and the one starting at SA[2], <c>"ippi$"</c>. Such prefix is the string <c>"i"</c>, |
| | | 21 | | /// therefore <c>LCP[1] = 1</c>. |
| | | 22 | | /// <br/> |
| | | 23 | | /// - The 3-rd item of the LCP Array of S is the length of the prefix in common between the suffix starting at |
| | | 24 | | /// SA[2], <c>"ippi$"</c>, and the one starting at SA[3], <c>"issippi$"</c>. Such prefix is again the string |
| | | 25 | | /// <c>"i"</c>, therefore <c>LCP[2] = 1</c>. |
| | | 26 | | /// <br/> |
| | | 27 | | /// - etc... |
| | | 28 | | /// </example> |
| | 82 | 29 | | public record struct LcpArray(IEnumerable<int> Lengths); |