---
title: LCP array
slug: lcp-array
qid: 
snapshot: enwiki-001374390487
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1374390487
tags: [11060667, 22906067, 22985424, 23118434, 23508058, 23603337, 24107591, 24107594, 24745114, 28269683, 59230396, 59230866, 60231876, 72655480]
---

# LCP array

> [!note] Provenance
> Snapshot `enwiki-001374390487` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1374390487> · Licensed CC BY-SA 4.0

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.

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. Let A be the suffix array of the string S=s_1,s_2,\ldots s_{n-1}\$ of length n , where \$ is a sentinel letter that is unique and lexicographically smaller than any other character. Let S[i,j] denote the substring of S ranging from i to j . Thus, S[A[i], n] is the i th smallest suffix of S . Let \operatorname{lcp}(v,w) denote the length of the longest common prefix between two strings v and w . Then the LCP array H[1,n] is an integer array of size n such that H[1] is undefined and H[i]=\operatorname{lcp}(S[A[i-1],n],S[A[i],n]) for every 1 . Thus H[i] stores the length of longest common prefix of the lexicographically 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. Consider the string S = \textrm{banana\$} : and its corresponding sorted suffix array A : Suffix array with suffixes written out underneath vertically: Then the LCP array H is constructed by comparing lexicographically consecutive suffixes to determine their longest common prefix: So, for example, H[4]=3 is the length of the longest common prefix \text{ana} shared by the suffixes A[3] = S[4,7] = \textrm{ana\$} and A[4] = S[2,7] = \textrm{anana\$} . Note that H[1] is undefined, since there is no lexicographically smaller suffix. lcp(P,M)==k The trick now is that LCP-LR is precomputed such that an O(1) -lookup tells us the longest common prefix of M and M' , \mathrm{lcp}(M,M') . We already know (from the previous step) that M itself has a prefix of k characters in common with P : \mathrm{lcp}(P,M)=k . Now there are three possibilities: Case 1: k , i.e. P has fewer prefix characters in common with M than M has in common with M'. This means the (k+1)-th character of M' is the same as that of M, and since P is lexicographically larger than M, it must be lexicographically larger than M', too. So we continue in the right half (M',...,R). Case 2: k > \mathrm{lcp}(M,M') , i.e. P has more prefix characters in common with M than M has in common with M' . Consequently, if we were to compare P to M' , the common prefix would be smaller than k , and M' would be lexicographically larger than P , so, without actually making the comparison, we continue in the left half (M,\dots,M') . Case 3: k = \mathrm{lcp}(M,M') . So M and M' are both identical with P in the first k characters. To decide whether we continue in the left or right half, it suffices to compare P to M' starting from the (k+1) th character. We continue recursively. The overall effect is that no character of P is compared to any character of the text more than once (for details see ). The total number of character comparisons is bounded by m , so the total complexity is indeed O(m+\log N) . We still need to precompute LCP-LR so it is able to tell us in O(1) time the lcp between any two entries of the suffix array. We know the standard LCP array gives us the lcp of consecutive entries only, i.e. \mathrm{lcp}(i-1,i) for any i . However, M and M' in the description above are not necessarily consecutive entries. The key to this is to realize that only certain ranges (L,\dots,R) will ever occur during the binary search: It always starts with (0, \dots,N) and divides that at the center, and then continues either left or right and divide that half again and so forth. Another way of looking at it is : every entry of the suffix array occurs as central point of exactly one possible range during binary search. So there are exactly N distinct ranges (L\dots M\dots R) that can possibly play a role during binary search, and it suffices to precompute \mathrm{lcp}(L,M) and \mathrm{lcp}(M,R) for those N possible ranges. So that is 2N distinct precomputed values, hence LCP-LR is O(N) in size. Moreover, there is a straightforward recursive algorithm to compute the 2N values of LCP-LR in O(N) time from the standard LCP array. To sum up: It is possible to compute LCP-LR in O(N) time and O(2N)=O(N) space from LCP. Using LCP-LR during binary search helps accelerate the search procedure from O(M\log N) to O(M+\log N) . We can use two binary searches to determine the left and right end of the match range for P , and the length of the match range corresponds with the number of occurrences for P. Given the suffix array A and the LCP array H of a string S=s_1,s_2,\ldots s_n\$ of length n+1 , its suffix tree ST can be constructed in O(n) time based on the following idea: Start with the partial suffix tree for the lexicographically smallest suffix and repeatedly insert the other suffixes in the order given by the suffix array. Let ST_{i} be the partial suffix tree for 0\leq i \leq n . Further let d(v) be the length of the concatenation of all path labels from the root of ST_i to node v . [[File:Constructing the suffix tree of banana based on the suffix array and the LCP array - Case 1.pdf|thumb|400px|Case 1 ( d(v)=H[i+1] ): Suppose the suffixes a\$ , ana\$ , anana\$ and banana$ of the string S=banana$ are already added to the suffix tree. Then the suffix na\$ is added to the tree as shown in the picture. The rightmost path is highlighted in red. Start with ST_0 , the tree consisting only of the root. To insert A[i+1] into ST_i , walk up the rightmost path beginning at the recently inserted leaf A[i] to the root, until the deepest node v with d(v) \leq H[i+1] is reached. We need to distinguish two cases: d(v)=H[i+1] : This means that the concatenation of the labels on the root-to- v path equals the longest common prefix of suffixes A[i] and A[i+1] . In this case, insert A[i+1] as a new leaf x of node v and label the edge (v,x) with S[A[i+1]+H[i+1],n] . Thus the edge label consists of the remaining characters of suffix A[i+1] that are not already represented by the concatenation of the labels of the root-to- v path. This creates the partial suffix tree ST_{i+1} . [[File:Constructing the suffix tree of banana based on the suffix array and the LCP array - Case 2.pdf|thumb|400px|Case 2 ( d(v) ): In order to add suffix nana\$ , the edge to the previously inserted suffix na\$ has to be split up. The new edge to the new internal node is labeled with the longest common prefix of the suffixes na$ and nana\$ . The edges connecting the two leaves are labeled with the remaining suffix characters that are not part of the prefix. d(v) : This means that the concatenation of the labels on the root-to- v path displays less characters than the longest common prefix of suffixes A[i] and A[i+1] and the missing characters are contained in the edge label of v 's rightmost edge. Therefore, we have to split up that edge as follows: Let w be the child of v on ST_i 's rightmost path. Delete the edge (v,w) . Add a new internal node y and a new edge (v,y) with label S[A[i]+d(v),A[i]+H[i+1]-1] . The new label consists of the missing characters of the longest common prefix of A[i] and A[i+1] . Thus, the concatenation of the labels of the root-to- y path now displays the longest common prefix of A[i] and A[i+1] . Connect w to the newly created internal node y by an edge (y,w) that is labeled S[A[i]+H[i+1],A[i]+d(w)-1] . The new label consists of the remaining characters of the deleted edge (v,w) that were not used as the label of edge (v,y) . Add A[i+1] as a new leaf x and connect it to the new internal node y by an edge (y,x) that is labeled S[A[i+1]+H[i+1],n] . Thus the edge label consists of the remaining characters of suffix A[i+1] that are not already represented by the concatenation of the labels of the root-to- v path. This creates the partial suffix tree ST_{i+1} . A simple amortization argument shows that the running time of this algorithm is bounded by O(n) : The nodes that are traversed in step i by walking up the rightmost path of ST_i (apart from the last node v ) are removed from the rightmost path, when A[i+1] is added to the tree as a new leaf. These nodes will never be traversed again for all subsequent steps j>i . Therefore, at most 2n nodes will be traversed in total. The LCP array H only contains the length of the longest common prefix of every pair of consecutive suffixes in the suffix array A . However, with the help of the inverse suffix array A^{-1} ( A[i]= j \Leftrightarrow A^{-1}[j]= i , i.e. the suffix S[j,n] that starts at position j in S is stored in position A^{-1}[j] in A ) and constant-time range minimum queries on H , it is possible to determine the length of the longest common prefix of arbitrary suffixes in O(1) time. Because of the lexicographic order of the suffix array, every common prefix of the suffixes S[i,n] and S[j,n] has to be a common prefix of all suffixes between i 's position in the suffix array A^{-1}[i] and j 's position in the suffix array A^{-1}[j] . Therefore, the length of the longest prefix that is shared by all of these suffixes is the minimum value in the interval H[A^{-1}[i]+1,A^{-1}[j . This value can be found in constant time if H is preprocessed for range minimum queries. Thus given a string S of length n and two arbitrary positions i,j in the string S with A^{-1}[i] , the length of the longest common prefix of the suffixes S[i,n] and S[j,n] can be computed as follows: \operatorname{LCP}(i,j)=H[\operatorname{RMQ}_H(A^{-1}[i]+1,A^{-1}[j])] . ==External links== Mirror of the ad-hoc-implementation of the code described in SDSL: Succinct Data Structure Library - Provides various LCP array implementations, Range Minimum Query (RMQ) support structures and many more succinct data structures Bottom-up suffix tree traversal emulated using suffix array and LCP array (Java) Text-Indexing project (linear-time construction of suffix trees, suffix arrays, LCP array and Burrows–Wheeler Transform)
