A Taxonomy of LCP-Array Construction Algorithms

In a landmark paper, Weiner [43] presented the concept of suffix trees and devised the first linear-time construction algorithm. For several decades, the suffix tree was the data structure in stringology, because it can be used to efficiently solve a “myriad” of string processing problems [4]. For instance, with the help of the suffix tree, exact pattern matching can be done in $O(m)$ time (assuming a constant alphabet size), where $m$ is the length of the pattern searched for. It should be pointed out that the search time is independent of the text length $n$.

The suffix array was devised by Manber and Myers [30] and independently by Gonnet et al. [19] under the name PAT array. Ten years later, it was shown independently and contemporaneously by Kärkkäinen and Sanders [23], Kim et al. [26], Ko and Aluru [27], and Hon et al. [20] that a direct linear-time construction of the suffix array is possible.

The $\mathrm{𝖫𝖢𝖯}$-array first appeared in the seminal paper of Manber and Myers [30], where it was called $Hgt$ array. The authors presented an $O(n\log n)$ time LCP-array construction algorithm (LACA for short) and showed that the augmentation of classical binary search with the $\mathrm{𝖫𝖢𝖯}$-array enables exact pattern matching on the suffix array in $O(m+\log n)$ time. The first linear-time LACA was devised by Kasai et al. [25]. They also demonstrated the importance of the $\mathrm{𝖫𝖢𝖯}$-array by presenting a linear-time algorithm that simulates the bottom-up traversal of a suffix tree with a suffix array and the $\mathrm{𝖫𝖢𝖯}$-array. Their work was taken one step further by Abouelhoda et al. [1], who showed that suffix trees can be completely replaced with enhanced suffix arrays. An enhanced suffix array is the combination of the suffix array with augmenting data structures, which depend on the application at hand. For example, exact pattern matching can be done in $O(m)$ time with the suffix array, the $\mathrm{𝖫𝖢𝖯}$-array, and constant-time range minimum queries [16] on the $\mathrm{𝖫𝖢𝖯}$-array [1] – again assuming constant alphabet size; for non-constant alphabet sizes $\sigma$ one can extend this idea to achieve $O(m\log \sigma )$ running time [15]. Algorithms on enhanced suffix arrays are not only more space efficient than those on suffix trees, but they are also faster and easier to implement. Since the $\mathrm{𝖫𝖢𝖯}$-array is of utmost importance in this context, it has been studied extensively.

Let $S$ be a text of length $n$ on an ordered alphabet $\mathrm{\Sigma }$ of constant size $\sigma$. We assume that $S$ has the sentinel $\mathrm{\$}\in \mathrm{\Sigma }$ at the end (and nowhere else), which is smaller than any other character. For $1\le i\le n$, $S[i]$ denotes the character at position $i$ in $S$. For $i\le j$, $S[i,j]$ denotes the substring of $S$ starting at position $i$ and ending at position $j$. Furthermore, $S_i$ denotes the $i$-th suffix $S[i,n]$ of $S$.

The suffix array $\mathrm{𝖲𝖠}$ of the text $S$ is an array of integers in the range $1$ to $n$ specifying the lexicographic ordering of the $n$ suffixes of $S$, that is, it satisfies . The suffix array can be built in linear time; we refer to the overview article of [37] for suffix array construction algorithms and to [35] for recent developments.

The inverse suffix array $\mathrm{𝖨𝖲𝖠}$ is an array of size $n$ such that for any $i$ with $1\le i\le n$ the equality $\mathrm{𝖨𝖲𝖠}[\mathrm{𝖲𝖠}[i]]=i$ holds. Obviously, it takes only linear time to invert the suffix array.

The $\mathrm{𝖫𝖢𝖯}$-array contains the lengths of longest common prefixes between consecutive suffixes in $\mathrm{𝖲𝖠}$. Formally, the $\mathrm{𝖫𝖢𝖯}$-array is an array such that $\mathrm{𝖫𝖢𝖯}[1]=\perp$ and $\mathrm{𝖫𝖢𝖯}[i]=\mathrm{𝗅𝖼𝗉}(S_{\mathrm{𝖲𝖠}[i-1]},S_{\mathrm{𝖲𝖠}[i]})$ for $2\le i\le n$, where $\mathrm{𝗅𝖼𝗉}(u,v)$ denotes the length of the longest common prefix between two strings $u$ and $v$. Here the value $\mathrm{𝖫𝖢𝖯}[1]$ is undefined, but – depending on the application – it may make sense to define it as $0$ or $-1$. Table 1 shows the $\mathrm{𝖫𝖢𝖯}$-array of the string $S=mississippi\mathrm{\$}$.

The Burrows-Wheeler transform [9] converts $S$ into the string $\mathrm{𝖡𝖶𝖳}[1,n]$ defined by $\mathrm{𝖡𝖶𝖳}[i]=S[\mathrm{𝖲𝖠}[i]-1]$ for all $i$ with $\mathrm{𝖲𝖠}[i]\ne 1$ and $\mathrm{𝖡𝖶𝖳}[i]=\mathrm{\$}$ otherwise. Given the suffix array, this transformation takes only linear time.

The $\psi$-array is an array of size $n$ such that $\psi [1]=\mathrm{𝖨𝖲𝖠}[1]$ and $\psi [i]=\mathrm{𝖨𝖲𝖠}[\mathrm{𝖲𝖠}[i]+1]$ for all $i$ with $2\le i\le n$. That is, $\psi [i]$ is the index at which the suffix $S_{\mathrm{𝖲𝖠}[i]+1}$ occurs in the suffix array. The $\psi$-array is the inverse of the $LF$-array, which can easily be computed in linear time from the $\mathrm{𝖡𝖶𝖳}$; see e.g. [34, Section 7.2.2].

The $C$-array is an array of size $\sigma$. For $c\in \mathrm{\Sigma }$, the entry $C[c]$ is defined as follows: if we consider all characters in $\mathrm{\Sigma }$ that are smaller than $c$, then $C[c]$ is the overall number of their occurrences in $S$.

We first present Kasai et al.’s LACA [25], which computes the $\mathrm{𝖫𝖢𝖯}$-array from the string $S$, its suffix array $\mathrm{𝖲𝖠}$, and its inverse suffix array $\mathrm{𝖨𝖲𝖠}$; see Algorithm 1. It starts with the longest suffix $S_i=S_1$ of $S$ (so $i=1$), computes $j=\mathrm{𝖨𝖲𝖠}[i]$ and then $\mathrm{𝖫𝖢𝖯}[j]$ by a left-to-right comparison of the characters in $S_i=S_{\mathrm{𝖲𝖠}[j]}$ and its immediately preceding suffix $S_k=S_{\mathrm{𝖲𝖠}[j-1]}$ in the suffix array. The same is done for the other suffixes $S_i$ of $S$ by incrementing $i$ successively. As we shall see, some character comparisons can safely be skipped.

In our example, Algorithm 1 first compares $S_1=mississippi\mathrm{\$}$ with $S_2=ississippi\mathrm{\$}$ and sets $\mathrm{𝖫𝖢𝖯}[j]=\mathrm{𝖫𝖢𝖯}[6]=0$. In the next iteration of the for-loop, it compares $S_2=ississippi\mathrm{\$}$ with $S_5=issippi\mathrm{\$}$ and sets $\mathrm{𝖫𝖢𝖯}[j]=\mathrm{𝖫𝖢𝖯}[5]=4$. In the following iterations of the for-loop the underlined characters in $S=mi\underset{¯}{ssi}ssippi\mathrm{\$}$ will be skipped in further comparisons of adjacent suffixes. For example, in the third iteration, Algorithm 1 must compare $S_3=ssissippi\mathrm{\$}$ with $S_6=ssippi\mathrm{\$}$ and the first three characters will be skipped in the comparison. To prove the correctness of Algorithm 1, we must show that if $\mathrm{\ell }>1$ characters match in iteration $i$ of the for-loop, then at least $\mathrm{\ell }-1$ characters match in iteration $i+1$. So suppose that the longest common prefix of $S_i$ and its preceding suffix $S_k$ is $c\omega$, where $c$ is a character and $\omega$ is a string of length $\mathrm{\ell }-1\ge 1$. In the next iteration, Algorithm 1 compares $S_{i+1}$ with its preceding suffix, which is not necessarily $S_{k+1}$ as in the example above. However, since $S_k=c\omega u$ is lexicographically smaller than $S_i=c\omega v$, it follows that $S_{k+1}=\omega u$ is lexicographically smaller than $S_{i+1}=\omega v$. Moreover, all the suffixes in between $S_{k+1}$ and $S_{i+1}$ must share the prefix $\omega$ because the suffixes are ordered lexicographically. In particular, $S_{i+1}$ and its preceding suffix have $\omega$ as a common prefix. Therefore, $\mathrm{\ell }-1$ characters (namely $\omega$) can be skipped in the comparison of $S_{i+1}$ and its preceding suffix. If $S_{k+1}$ immediately precedes $S_{i+1}$ in the suffix array, then we can directly conclude that their longest common prefix is $\omega$; otherwise further character comparisons are required to determine their longest common prefix. Obviously, $S_{k+1}$ precedes $S_{i+1}$ if $\mathrm{𝖡𝖶𝖳}[j^{\prime }]=\mathrm{𝖡𝖶𝖳}[j^{\prime }-1]$, where $j^{\prime }=\mathrm{𝖨𝖲𝖠}[i+1]$. This result is summarized in the next lemma, which will be important later. The first proof of Lemma 1 can be found in [25]. A value $\mathrm{𝖫𝖢𝖯}[j]$ is called reducible if $\mathrm{𝖡𝖶𝖳}[j]=\mathrm{𝖡𝖶𝖳}[j-1]$; otherwise it is called irreducible.

It will now be shown that Algorithm 1 constructs the $\mathrm{𝖫𝖢𝖯}$-array in $O(n)$ time. We use an amortized analysis to show that the while-loop is executed at most $2n$ times. It is readily verified that this implies the linear run-time. Each comparison in the while-loop ends with a mismatch, so there are $n-1$ mismatches (redundant character comparisons) in total. If a position $p$ in $S$ is involved in a match, then this particular occurrence of character $S[p]$ will be skipped in further suffix comparisons. More precisely, if we have $S[k+\mathrm{\ell }]=S[i+\mathrm{\ell }]$ in the while-loop, then $p=i+\mathrm{\ell }$ will not appear on the right-hand-side of a character comparison again. So there are at most $n$ matches. To illustrate the argument, the positions in our example text that are involved in a match are marked by underlining the respective character in $S=m\underset{¯}{issis}s\underset{¯}{ip}pi\mathrm{\$}$. Since every position is marked at most once (because it is skipped in further comparisons), it is clear that the overall number of character comparisons is $n-1$ (mismatches) plus the number of underlined characters.

In Algorithm 1, the text $S$ as well as the arrays $\mathrm{𝖲𝖠}$, $\mathrm{𝖨𝖲𝖠}$, and $\mathrm{𝖫𝖢𝖯}$ should be randomly accessible. Under the common assumption that an entry in $\mathrm{𝖲𝖠}$ takes $4$ bytes, each of the arrays $\mathrm{𝖲𝖠}$, $\mathrm{𝖨𝖲𝖠}$, and $\mathrm{𝖫𝖢𝖯}$ requires $4n$ bytes. Consequently, for an 8 bit alphabet, Algorithm 1 needs $13n$ bytes of working memory.

In the context of compressed suffix trees, Mäkinen [29, Proposition 3.2] first showed that the $\mathrm{𝖫𝖢𝖯}$-array can be constructed with less working space. Manzini [31] observed that the additional array $\mathrm{𝖨𝖲𝖠}$ is superfluous because it is possible to store the required information about $\mathrm{𝖨𝖲𝖠}$ in the $\mathrm{𝖫𝖢𝖯}$-array itself. If the $\mathrm{𝖫𝖢𝖯}$-array initially stores the $\psi$-array, then the cell $\mathrm{𝖫𝖢𝖯}[j]$ contains the value $\mathrm{𝖨𝖲𝖠}[i+1]$ in iteration $i$ of the for-loop of Algorithm 2. That is, variable $next$ gets the value $\mathrm{𝖨𝖲𝖠}[i+1]$ in line 4 and $\mathrm{𝖫𝖢𝖯}[j]$ can safely be overwritten in line 9. The correctness of Algorithm 2 follows directly from this fact. Algorithm 2 requires $9n$ bytes of working memory because it needs random access to the text and both input arrays.

Manzini [31] proposed another LACA, which saves even more space by overwriting the suffix array. This LACA is based on Lemma 1: if $\mathrm{𝖫𝖢𝖯}[j]$ is reducible, then one can immediately set $\mathrm{𝖫𝖢𝖯}[j]\leftarrow \mathrm{\ell }$ because the character comparisons in lines 7-8 of Algorithm 2 are superfluous. It follows as a consequence that in this case the assignment $k\leftarrow \mathrm{𝖲𝖠}[j-1]$ is superfluous, too. In other words, the value $\mathrm{𝖲𝖠}[j-1]$ is required only if $\mathrm{𝖫𝖢𝖯}[j]$ is irreducible. In a preprocessing phase, Manzini’s second LACA determines the values in the suffix array $\mathrm{𝖲𝖠}$ that are actually required and stores them in an auxiliary array. The auxiliary array is then used instead of $\mathrm{𝖲𝖠}$ and $\mathrm{𝖲𝖠}$ can safely be overwritten. However, this LACA is of limited value in practice because in most applications the suffix array is needed as well.

Kärkkäinen, Manzini, and Puglisi [22] proposed a variant of Kasai et al.’s algorithm, which first computes a permuted $\mathrm{𝖫𝖢𝖯}$-array (the $\mathrm{𝖯𝖫𝖢𝖯}$-array) with the help of the so-called $\mathrm{\Phi }$-array and then derives the $\mathrm{𝖫𝖢𝖯}$-array from the $\mathrm{𝖯𝖫𝖢𝖯}$-array. They called it “$\mathrm{\Phi }$-algorithm” because it uses the $\mathrm{\Phi }$-array, which “is in some way symmetric to the $\psi$ array.”

The $\mathrm{\Phi }$-array and the $\mathrm{𝖯𝖫𝖢𝖯}$-array, respectively, are defined as follows: For all $i$ with $1\le i\le n$ let

Fig. 1 shows our example. So in the suffix array $\mathrm{𝖲𝖠}$, the suffix $S_i$ is immediately preceded by the suffix $S_{\mathrm{\Phi }[i]}$ unless $\mathrm{\Phi }[i]=0$. Note that we have $\mathrm{\Phi }[n]=0$ because we assume that $S$ is terminated by $\mathrm{\$}$. For $j\ne 1$, we have

In case $j=1$, Equation (1) holds also true: $\mathrm{𝖫𝖢𝖯}[1]=\perp$ and $\mathrm{𝖯𝖫𝖢𝖯}[\mathrm{𝖲𝖠}[1]]=\mathrm{𝖯𝖫𝖢𝖯}[n]=\perp$ because $\mathrm{\Phi }[n]=0$. Thus, the $\mathrm{𝖯𝖫𝖢𝖯}$-array is a permutation of the $\mathrm{𝖫𝖢𝖯}$-array. The difference between the two arrays is that the lcp-values occur in text order (position order) in the $\mathrm{𝖯𝖫𝖢𝖯}$-array, whereas they occur in suffix array order (lexicographic order) in the $\mathrm{𝖫𝖢𝖯}$-array. The pseudocode of the $\mathrm{\Phi }$-algorithm is shown in Algorithm 3. Its properties (correctness, linear run-time) can be shown as in the analysis of Algorithm 1.

Experimental comparisons of Algorithm 1 and the $\mathrm{\Phi }$-algorithm can be found in [22, 18]. The bottom line is that the $\mathrm{\Phi }$-algorithm is faster because of better memory locality: it merely needs sequential access to the $\mathrm{\Phi }$-array and the $\mathrm{𝖯𝖫𝖢𝖯}$-array in its second for-loop. Consequently, these arrays can be streamed and the number of possible cache misses is limited to $3n$: $n$ in the computation of the $\mathrm{\Phi }$-array, $n$ in line 6,²²2Remark: If $\mathrm{𝖯𝖫𝖢𝖯}[i]$ is reducible, then $\mathrm{\Phi }[i]=\mathrm{\Phi }[i-1]+1$ and hence $S[\mathrm{\Phi }[i]]$ is cached. and $n$ in the conversion of the $\mathrm{𝖯𝖫𝖢𝖯}$-array into the $\mathrm{𝖫𝖢𝖯}$-array (in virtually all applications lcp-values are required to be in suffix array order). By contrast, there can be up to $4n$ cache misses in Algorithm 1 (including the computation of $\mathrm{𝖨𝖲𝖠}$).

If we assume that the arrays $\mathrm{𝖲𝖠}$, $\mathrm{\Phi }$, $\mathrm{𝖯𝖫𝖢𝖯}$, and $\mathrm{𝖫𝖢𝖯}$ are kept in working memory, then Algorithm 3 requires $17n$ bytes RAM. However, the algorithm merely needs random access to the $\mathrm{\Phi }$-array in the first for-loop, to the text in the second for-loop, and to the $\mathrm{𝖯𝖫𝖢𝖯}$-array in the third for-loop. All other arrays can be streamed from or to disk. Thus, $9n$ bytes of RAM are sufficient.

Kärkkäinen et al. [22] presented another algorithm for computing the $\mathrm{𝖯𝖫𝖢𝖯}$-array based on irreducible $\mathrm{𝖯𝖫𝖢𝖯}$-values. We call a value $\mathrm{𝖯𝖫𝖢𝖯}[i]$ reducible if $S[i-1]=S[\mathrm{\Phi }[i]-1]$; otherwise it is called irreducible. The proof of the next lemma is similar to that of Lemma 1.

The above-mentioned algorithm first determines all irreducible $\mathrm{𝖯𝖫𝖢𝖯}$-values in a brute-force manner: each $\mathrm{𝖯𝖫𝖢𝖯}$-value is computed by comparing the respective suffixes from the very beginning. Afterwards, it uses Lemma 2 to compute the remaining reducible $\mathrm{𝖯𝖫𝖢𝖯}$-values. The authors showed that the sum of all irreducible $\mathrm{𝖯𝖫𝖢𝖯}$-values is at most $2n\log n$. Hence, the overall run-time is $O(n\log n)$. An experimental comparison of this algorithm and the $\mathrm{\Phi }$-algorithm showed that the $\mathrm{\Phi }$-algorithm is faster in practice; see [22].

The LCP-array can also be computed while sorting the suffixes lexicographically, which we show here for two well-known suffix array construction algorithms DC3 [24] and SAIS [33]. The adaptions to the LCP-array computation were described in the original article for DC3, and by Bingmann et al. for SAIS [8]. Intuitively, it seems clear that LCP-array computation during suffix array construction should be possible, as any suffix sorting algorithm must, at least implicitly, determine the lcp-values between lexicographically adjacent suffixes to determine their order, for otherwise it could not make the right decisions on the order of suffixes.

Next, we will present a LACA that is based on the $\mathrm{𝖡𝖶𝖳}$ of $S$ [7]. We start with some prerequisites.

Let $\omega$ be a substring of $S$. The $\omega$-interval is the interval $[i,j]$ such that $\omega$ is a common prefix of $S_{\mathrm{𝖲𝖠}[i]},S_{\mathrm{𝖲𝖠}[i+1]},\mathrm{\dots },S_{\mathrm{𝖲𝖠}[j]}$, but neither of $S_{\mathrm{𝖲𝖠}[i-1]}$ nor of $S_{\mathrm{𝖲𝖠}[j+1]}$. For example, in Table 2 one can see that the $miss$-interval is $[6,6]$, while the $iss$-interval is $[4,5]$. Since the empty string $\epsilon$ is a common prefix of all suffixes of $S$, the $\epsilon$-interval is $[1,n]$. The LACA in Algorithm 4 is based on the procedure $\mathrm{𝑔𝑒𝑡𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠}$, which has the following functionality: For an $\omega$-interval $[i,j]$, the call $\mathrm{𝑔𝑒𝑡𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠}([i,j])$ returns the list of all $c\omega$-intervals, where $c\in \mathrm{\Sigma }$ and $c\omega$ is a substring of $S$. In our example, $\mathrm{𝑔𝑒𝑡𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠}$ applied to the $\epsilon$-interval $[1,12]$ generates the $\mathrm{\$}$-interval $[1,1]$, the $i$-interval $[2,5]$, the $m$-interval $[6,6]$, the $p$-interval $[7,8]$ and the $s$-interval $[9,12]$. Beller et al. [7] describe an implementation of the procedure $\mathrm{𝑔𝑒𝑡𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠}$ that is based on the wavelet tree of the $\mathrm{𝖡𝖶𝖳}$ of $S$. A call to $\mathrm{𝑔𝑒𝑡𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠}([i,j])$ takes $O(k\log \sigma )$ time if it returns a list with $k$ intervals (so each interval can be generated in $O(\log \sigma )$ time).

Algorithm 4 shows how the $\mathrm{𝖫𝖢𝖯}$-array of a string $S$ can be obtained solely based on the procedure $\mathrm{𝑔𝑒𝑡𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠}$. The algorithm maintains a queue $Q$, which initially contains the $\epsilon$-interval $[1,n]$. Moreover, the variable $\mathrm{\ell }$ stores the current lcp-value (initially, $\mathrm{\ell }=-1$) and $size$ memorizes how many elements there are in $Q$ that correspond to the current lcp-value (initially, $size=1$). Algorithm 4 computes lcp-values in increasing order (first the artificial entry $\mathrm{𝖫𝖢𝖯}[n+1]=-1$, then the $0$ entries, and so on) as follows: whenever it dequeues an element from $Q$, say the $\omega$-interval $[lb,rb]$ where $|\omega |=\mathrm{\ell }+1$, it tests whether $\mathrm{𝖫𝖢𝖯}[rb+1]=\perp$. If so, it assigns $\mathrm{\ell }$ to $\mathrm{𝖫𝖢𝖯}[rb+1]$, generates all non-empty $c\omega$-intervals (where $c\in \mathrm{\Sigma }$) and adds them to (the back of) $Q$. Otherwise, it does nothing.

Let us illustrate the algorithm by computing the artificial $-1$ entry and all $0$ entries in the $\mathrm{𝖫𝖢𝖯}$-array of our example in Table 2. Initially, $\mathrm{\ell }=-1$ and the queue $Q$ contains the $\epsilon$-interval $[1,12]$. Consequently, the first interval that is pulled from the queue is the $\epsilon$-interval $[1,12]$ and $size$ is decreased by one. Since $\mathrm{𝖫𝖢𝖯}[12+1]=\perp$, case 1 in Algorithm 4 applies. Thus, $\mathrm{𝖫𝖢𝖯}[13]$ is set to $\mathrm{\ell }=-1$ and $\mathrm{𝑔𝑒𝑡𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠}([1,12])$ generates the $\mathrm{\$}$-interval $[1,1]$, the $i$-interval $[2,5]$, the $m$-interval $[6,6]$, the $p$-interval $[7,8]$ and the $s$-interval $[9,12]$. These intervals are put into the queue $Q$. In the second iteration of the while-loop, we have $size=0$. Therefore, $\mathrm{\ell }=-1$ is increased by one and the variable $size$ gets the new value $|Q|$. At that point, the $size$ of $Q$ is $5$; so five intervals correspond to the new lcp-value $\mathrm{\ell }=0$. The second interval that is pulled from the queue is the $\mathrm{\$}$-interval $[1,1]$ and $size$ is decreased by one. Since $\mathrm{𝖫𝖢𝖯}[1+1]=\perp$, case 1 in Algorithm 4 applies. Thus, $\mathrm{𝖫𝖢𝖯}[2]$ is set to $\mathrm{\ell }=0$ and the $i\mathrm{\$}$-interval $[2,2]$, which is the only interval in the list returned by $\mathrm{𝑔𝑒𝑡𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠}([1,1])$, is added to the queue. Next, the $i$-interval $[2,5]$ is dequeued (and $size$ is decreased by one). Again, case 1 applies because $\mathrm{𝖫𝖢𝖯}[5+1]=\perp$. So $\mathrm{𝖫𝖢𝖯}[6]$ is set to $\mathrm{\ell }=0$, $\mathrm{𝑔𝑒𝑡𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠}([2,5])$ returns the list $[[6,6],[7,7],[9,10]]$, and the intervals in the list are added to the queue $Q$. When the $m$-interval $[6,6]$ is dequeued, $size$ is decreased by one, $\mathrm{𝖫𝖢𝖯}[7]$ is set to $\mathrm{\ell }=0$, but no new interval is added to the queue (observe that $\mathrm{𝑔𝑒𝑡𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑠}$ does not generate the $\mathrm{\$}m$-interval because $\mathrm{\$}m$ is not a substring of $S$). Then the $p$-interval is dequeued, $size$ is decreased by one, $\mathrm{𝖫𝖢𝖯}[9]$ is set to $0$, and the intervals $[3,3]$ and $[8,8]$ (the $ip$- and the $pp$-interval) are enqueued. Finally, the $s$-interval $[9,12]$ is pulled from the queue. Again, $size$ is decreased by one; it now has the value $0$. Because $\mathrm{𝖫𝖢𝖯}[12+1]=-1$, case 2 in Algorithm 4 applies. In the next iteration of the while-loop, $\mathrm{\ell }$ is increased by one and $size$ is set to the current size $6$ of $Q$. At that point in time, the six elements in $Q$ are the following intervals that correspond to the lcp-value $\mathrm{\ell }=1$:

where the notation ${[lb,rb]}_{\omega }$ indicates that the interval $[lb,rb]$ is the $\omega$-interval. The reader is invited to compute all $1$ entries in the $\mathrm{𝖫𝖢𝖯}$-array by executing the algorithm by hand.

We have only scratched the surface of LCP-array construction and reviewed some classic algorithms, but we did not cover results on the efficient storage of lcp-values, such as sampled [41] or compressed [13, 39] LCP-arrays. There are also variants of LCP-arrays, such as for labeled graphs [3], spectra [2], or Wheeler DFAs [11], or with mismatches [32], which were all not covered here. We also did not look at more advanced models of computation, like parallel shared or distributed memory [17, 40] or external memory [8, 21]. Finally, LCP-arrays for collections of strings have also been considered [12, 28]. All citations in this subsection should only be seen as a point of entry for further literature research, as they are far from exhaustive. We close this review article by mentioning that for large repetitive data sets the currently best practical algorithm is based on prefix free parsing [38, Lemma 2].