Class

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 length of the prefix in common between the suffixes starting at SA[i] and SA[i + 1], where SA is the Suffix Array of S, for each i from 0 to n - 1 excluded.

Inheritance
System.Object
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.SuffixArrays.LongestCommonPrefix
Assembly: MoreStructures.dll
Syntax
public class  : IEquatable<>
Remarks

The LCP Array of a string of length n has n - 1 items.

Examples

Given the string S = "mississippi$" with terminator char '$', S has Suffix Array SA = { 11, 10, 7, 4, ... }.

  • The 1-st item of the LCP Array of S is the length of the prefix in common between the suffix starting at SA[0], "$", and the one starting at SA[1], "i$". Such prefix is the empty string, therefore LCP[0] = 0.
  • The 2-nd item of the LCP Array of S is the length of the prefix in common between the suffix starting at SA[1], "i$", and the one starting at SA[2], "ippi$". Such prefix is the string "i", therefore LCP[1] = 1.
  • The 3-rd item of the LCP Array of S is the length of the prefix in common between the suffix starting at SA[2], "ippi$", and the one starting at SA[3], "issippi$". Such prefix is again the string "i", therefore LCP[2] = 1.
  • etc...

Implements

System.IEquatable<T>

Extension Methods