# LCP array

LCP array
Type Array
Invented by Template:Harvtxt
Time complexity and space complexity
in big O notation
Average Worst case
Space ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$
Construction ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$

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 between pairs of consecutive suffixes in the sorted suffix array.

Augmenting the suffix array with the LCP array allows to efficiently simulate top-down and bottom-up traversals of the suffix tree,Template:SfnTemplate:Sfn speeds up pattern matching on the suffix arrayTemplate:Sfn and is a prerequisite for compressed suffix trees.Template:Sfn

## History

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

## Definition

Let ${\displaystyle A}$ be the suffix array of the string ${\displaystyle S=s_{1},s_{2},...s_{n}\}$ and let ${\displaystyle \operatorname {lcp} (v,w)}$ denote the length of the longest common prefix between two strings ${\displaystyle v}$ and ${\displaystyle w}$. Let further denote ${\displaystyle S[i,j]}$ the substring of ${\displaystyle S}$ ranging from ${\displaystyle i}$ to ${\displaystyle j}$.

Then the LCP array ${\displaystyle H[1,n]}$ is an integer array of size ${\displaystyle n}$ such that ${\displaystyle H[1]}$ is undefined and ${\displaystyle H[i]=\operatorname {lcp} (S[A[i-1],n],S[A[i],n])}$ for every ${\displaystyle 1. Thus ${\displaystyle H[i]}$ stores the length of longest common prefix of the lexicographically ${\displaystyle i}$'th smallest suffix and its predecessor in the suffix array.

## Example

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

 Template:Left header | i Template:Left header | S[i] 1 2 3 4 5 6 7 b a n a n a $and its corresponding suffix array ${\displaystyle A}$ :  Template:Left header | i Template:Left header | A[i] 1 2 3 4 5 6 7 7 6 4 2 1 5 3 Complete suffix array with suffixes itself : Template:Left header | i Template:Left header | A[i] Template:Left header | 1 Template:Left header | 2 Template:Left header | 3 Template:Left header | 4 Template:Left header | 5 1 2 3 4 5 6 7 7 6 4 2 1 5 3$ a a a b n n $n n a a a a a n$ n $n a a a n$ $a$

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

 Template:Left header | i Template:Left header | H[i] 1 2 3 4 5 6 7 ${\displaystyle \bot }$ 0 1 3 0 0 2

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

## Efficient Construction Algorithms

LCP array construction algorithms can be divided into two different categories: algorithms that compute the LCP array as a byproduct to the suffix array and algorithms that use an already constructed suffix array in order to compute the LCP values.

Template:Harvtxt provide an algorithm to compute the LCP array alongside the suffix array in ${\displaystyle O(n\log n)}$ time. Template:Harvtxt show that it is also possible to modify their ${\displaystyle O(n)}$ time algorithm such that it computes the LCP array as well. Template:Harvtxt present the first ${\displaystyle O(n)}$ time algorithm (FLAAP) that computes the LCP array given the text and the suffix array.

Assuming that each text symbol takes one byte and each entry of the suffix or LCP array takes 4 bytes, the major drawback of their algorithm is a large space occupancy of ${\displaystyle 13n}$ bytes, while the original output (text, suffix array, LCP array) only occupies ${\displaystyle 9n}$ bytes. Therefore Template:Harvtxt created a refined version of the algorithm of Template:Harvtxt (lcp9) and reduced the space occupancy to ${\displaystyle 9n}$ bytes. Template:Harvtxt provide another refinement of Kasai's algorithm (${\displaystyle \Phi }$-algorithm) that improves the running time. Rather than the actual LCP array, this algorithm builds the permuted LCP (PLCP) array, in which the values appear in text order rather than lexicographical order.

Template:Harvtxt provide two algorithms that although being theoretically slow (${\displaystyle O(n^{2})}$) were faster than the above mentioned algorithms in practice.

As of 2012, the currently fastest linear-time LCP array construction algorithm is due to Template:Harvtxt, which in turn is based on one of the fastest suffix array construction algorithms by Template:Harvtxt.

## Applications

As noted by Template:Harvtxt several string processing problems can be solved by the following kinds of tree traversals:

• bottom-up traversal of the complete suffix tree
• top-down traversal of a subtree of the suffix tree
• suffix tree traversal using the suffix links.

Template:Harvtxt show how to simulate a bottom-up traversal of the suffix tree using only the suffix array and LCP array. Template:Harvtxt enhance the suffix array with the LCP array and additional data structures and describe how this enhanced suffix array can be used to simulate all three kinds of suffix tree traversals. Template:Harvtxt reduce the space requirements of the enhanced suffix array by preprocessing the LCP array for range minimum queries. Thus, every problem that can be solved by suffix tree algorithms can also be solved using the enhanced suffix array.Template:Sfn

Deciding if a pattern ${\displaystyle P}$ of length ${\displaystyle m}$ is a substring of a string ${\displaystyle S}$ of length ${\displaystyle n}$ takes ${\displaystyle O(m\log n)}$ time if only the suffix array is used. By additionally using the LCP information, this bound can be improved to ${\displaystyle O(m+\log n)}$ time.Template:Sfn Template:Harvtxt show how to improve this running time even further to achieve optimal ${\displaystyle O(m)}$ time. Thus, using suffix array and LCP array information, the decision query can be answered as fast as using the suffix tree.

The LCP array is also an essential part of compressed suffix trees which provide full suffix tree functionality like suffix links and lowest common ancestor queries.Template:SfnTemplate:Sfn Furthermore it can be used together with the suffix array to compute the Lempel-Ziv LZ77 factorization in ${\displaystyle O(n)}$ time. Template:SfnTemplate:SfnTemplate:SfnTemplate:Sfn

The longest repeated substring problem for a string ${\displaystyle S}$ of length ${\displaystyle n}$ can be solved in ${\displaystyle \Theta (n)}$ time using both the suffix array ${\displaystyle A}$ and the LCP array. It is sufficient to perform a linear scan through the LCP array in order to find its maximum value ${\displaystyle v_{max}}$ and the corresponding index ${\displaystyle i}$ where ${\displaystyle v_{max}}$ is stored. The longest substring that occurs at least twice is then given by ${\displaystyle S[A[i],A[i]+v_{max}-1]}$.

The remainder of this section explains two applications of the LCP array in more detail: How the suffix array and the LCP array of a string can be used to construct the corresponding suffix tree and how it is possible to answer LCP queries for arbitrary suffixes using range minimum queries on the LCP array.

### Suffix Tree Construction

Given the suffix array ${\displaystyle A}$ and the LCP array ${\displaystyle H}$ of a string ${\displaystyle S=s_{1},s_{2},...s_{n}\}$ of length ${\displaystyle n+1}$, its suffix tree ${\displaystyle ST}$ can be constructed in ${\displaystyle 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 ${\displaystyle ST_{i}}$ be the partial suffix tree for ${\displaystyle 0\leq i\leq n}$. Further let ${\displaystyle d(v)}$ be the length of the concatenation of all path labels from the root of ${\displaystyle ST_{i}}$ to node ${\displaystyle v}$.

Start with ${\displaystyle S_{0}}$, the tree consisting only of the root. To insert ${\displaystyle A[i+1]}$ into ${\displaystyle ST_{i}}$, walk up the rightmost path beginning at the recently inserted leaf ${\displaystyle A[i]}$ to the root, until the deepest node ${\displaystyle v}$ with ${\displaystyle d(v)\leq H[i+1]}$ is reached.

We need to distinguish two cases:

1. Delete the edge ${\displaystyle (v,w)}$.
2. Add a new internal node ${\displaystyle y}$ and a new edge ${\displaystyle (v,y)}$ with label ${\displaystyle 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 ${\displaystyle A[i]}$ and ${\displaystyle A[i+1]}$. Thus, the concatenation of the labels of the root-to-${\displaystyle y}$ path now displays the longest common prefix of ${\displaystyle A[i]}$ and ${\displaystyle A[i+1]}$.
3. Connect ${\displaystyle w}$ to the newly created internal node ${\displaystyle y}$ by an edge ${\displaystyle (y,w)}$ that is labeled ${\displaystyle S[A[i]+H[i+1],A[i]+d(w)-1]}$. The new label consists of the remaining characters of the deleted edge ${\displaystyle (v,w)}$ that were not used as the label of edge ${\displaystyle (v,y)}$.
4. Add ${\displaystyle A[i+1]}$ as a new leaf ${\displaystyle x}$ and connect it to the new internal node ${\displaystyle y}$ by an edge ${\displaystyle (y,x)}$ that is labeled ${\displaystyle S[A[i+1]+H[i+1],n]}$. Thus the edge label consists of the remaining characters of suffix ${\displaystyle A[i+1]}$ that are not already represented by the concatenation of the labels of the root-to-${\displaystyle v}$ path.
5. This creates the partial suffix tree ${\displaystyle ST_{i+1}}$.

A simple amortization argument shows that the running time of this algorithm is bounded by ${\displaystyle O(n)}$:

The nodes that are traversed in step ${\displaystyle i}$ by walking up the rightmost path of ${\displaystyle ST_{i}}$ (apart from the last node ${\displaystyle v}$) are removed from the rightmost path, when ${\displaystyle A[i+1]}$ is added to the tree as a new leaf. These nodes will never be traversed again for all subsequent steps ${\displaystyle j>i}$. Therefore, at most ${\displaystyle 2n}$ nodes will be traversed in total.

### LCP queries for arbitrary suffixes

The LCP array ${\displaystyle H}$ only contains the length of the longest common prefix of every pair of consecutive suffixes in the suffix array ${\displaystyle A}$. However, with the help of the inverse suffix array ${\displaystyle A^{-1}}$ (${\displaystyle A[i]=j\Leftrightarrow A^{-1}[j]=i}$, i.e. the suffix ${\displaystyle S[j,n]}$ that starts at position ${\displaystyle j}$ in ${\displaystyle S}$ is stored in position ${\displaystyle A^{-1}[j]}$ in ${\displaystyle A}$) and constant-time range minimum queries on ${\displaystyle H}$, it is possible to determine the length of the longest common prefix of arbitrary suffixes in ${\displaystyle O(1)}$ time.

Because of the lexicographic order of the suffix array, every common prefix of the suffixes ${\displaystyle S[i,n]}$ and ${\displaystyle S[j,n]}$ has to be a common prefix of all suffixes between ${\displaystyle i}$'s position in the suffix array ${\displaystyle A^{-1}[i]}$ and ${\displaystyle j}$'s position in the suffix array ${\displaystyle 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 ${\displaystyle H[A^{-1}[i]+1,A^{-1}[j]]}$. This value can be found in constant time if ${\displaystyle H}$ is preprocessed for range minimum queries.

Thus given a string ${\displaystyle S}$ of length ${\displaystyle n}$ and two arbitrary positions ${\displaystyle i,j}$ in the string ${\displaystyle S}$ with ${\displaystyle A^{-1}[i], the length of the longest common prefix of the suffixes ${\displaystyle S[i,n]}$ and ${\displaystyle S[j,n]}$ can be computed as follows: ${\displaystyle \operatorname {LCP} (i,j)=H[\operatorname {RMQ} _{H}(A^{-1}[i]+1,A^{-1}[j])]}$.

## References

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

• {{#invoke:Citation/CS1|citation

|CitationClass=journal }}