LCP array

In computer science, the longest common prefix array (LCP array) is an auxiliary data structure to the suffix array. It stores the lengths of the longest common prefixes (LCPs) between all pairs of consecutive suffixes in a sorted suffix array. For example, if A := [aab, ab, abaab, b, baab] is a suffix array, the longest common prefix between A[1] = aab and A[2] = ab is a which has length 1, so H[2] = 1 in the LCP array H. Likewise, the LCP of A[2] = ab and A[3] = abaab is ab, so H[3] = 2. Augmenting the suffix array with the LCP array allows one to efficiently simulate top-down and bottom-up traversals of the suffix tree, speeds up pattern matching on the suffix array and is a prerequisite for compressed suffix trees.

History The LCP array was introduced in 1993, by Udi Manber and Gene Myers alongside the suffix array in order to improve the running time of their string search algorithm.

Definition Let A {\displaystyle A} be the suffix array of the string S = s 1 , s 2 , … s n − 1 $ {\displaystyle S=s_{1},s_{2},\ldots s_{n-1}\$} of length n {\displaystyle n} , where $ {\displaystyle \$} is a sentinel letter that is unique and lexicographically smaller than any other character. Let S [ i , j ] {\displaystyle S[i,j]} denote the substring of S {\displaystyle S} ranging from i {\displaystyle i} to j {\displaystyle j} . Thus, S [ A [ i ] , n ] {\displaystyle S[A[i],n]} is the i {\displaystyle i} th smallest suffix of S {\displaystyle S} . Let lcp ⁡ ( v , w ) {\displaystyle \operatorname {lcp} (v,w)} denote the length of the longest common prefix between two strings v {\displaystyle v} and w {\displaystyle w} . Then the LCP array H [ 1 , n ] {\displaystyle H[1,n]} is an integer array of size n {\displaystyle n} such that H [ 1 ] {\displaystyle H[1]} is undefined and H [ i ] = lcp ⁡ ( S [ A [ i − 1 ] , n ] , S [ A [ i ] , n ] ) {\displaystyle H[i]=\operatorname {lcp} (S[A[i-1],n],S[A[i],n])} for every 1 < i ≤ n {\displaystyle 1<i\leq n} . Thus H [ i ] {\displaystyle H[i]} stores the length of longest common prefix of the lexicographically i {\displaystyle i} th smallest suffix and its predecessor in the suffix array. Difference between LCP array and suffix array:

Suffix array: Represents the lexicographic rank of each suffix of an array. LCP array: Contains the maximum length prefix match between two consecutive suffixes, after they are sorted lexicographically.

Example Consider the string S = banana$ {\displaystyle S={\textrm {banana\$}}} :

and its corresponding sorted suffix array A {\displaystyle A} :

Suffix array with suffixes written out underneath vertically:

Then the LCP array H {\displaystyle H} is constructed by comparing lexicographically consecutive suffixes to determine their longest common prefix:

So, for example, H [ 4 ] = 3 {\displaystyle H[4]=3} is the length of the longest common prefix ana {\displaystyle {\text{ana}}} shared by the suffixes A [ 3 ] = S [ 4 , 7 ] = ana$ {\displaystyle A[3]=S[4,7]={\textrm {ana\$}}} and A [ 4 ] = S [ 2 , 7 ] = anana$ {\displaystyle A[4]=S[2,7]={\textrm {anana\$}}} . Note that H [ 1 ] {\displaystyle H[1]} is undefined, since there is no lexicographically smaller suffix.

… excerpt ends here. Continue reading the full article.