1. History

2. Definition

3. Example

4. Difference between suffix array and LCP array

5. LCP array usage in finding the number of occurrences of a pattern

6. Efficient construction algorithms

7. Applications
     Suffix tree construction    LCP queries for arbitrary suffixes  

8. Notes

9. References

10. External links

LCP array
Type	Array
Invented by{{!}} colspan="2" {{!}} {{harvtxt|Manber|Myers|1990}}
Time complexity and space complexity in big O notation
Average	Worst case
Space
Construction

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,{{sfn|Kasai|Lee|Arimura|Arikawa|2001}}{{sfn|Abouelhoda|Kurtz|Ohlebusch|2004}} speeds up pattern matching on the suffix array{{sfn|Manber|Myers|1993}} and is a prerequisite for compressed suffix trees.{{sfn|Ohlebusch|Fischer|Gog|2010}}

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.{{sfn|Manber|Myers|1993}} Gene Myers later became the vice president of Informatics Research at Celera Genomics, and Udi Manber the vice president of engineering at Google.

Definition

Let be the suffix array of the string and let denote the length of the longest common prefix between two strings and . Let further denote the substring of ranging from to .

Then the LCP array is an integer array of size such that is undefined and for every . Thus stores the length of longest common prefix of the lexicographically 'th smallest suffix and its predecessor in the suffix array.

Example

Consider the string :

and its corresponding sorted suffix array :

Complete suffix array with sorted suffixes itself:

Then the LCP array is constructed by comparing lexicographically consecutive suffixes to determine their longest common prefix:

So, for example, is the length of the longest common prefix shared by the suffixes and . Note that , since there is no lexicographically smaller suffix.

Difference between suffix array and LCP 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.

LCP array usage in finding the number of occurrences of a pattern

In order to find the number of occurrences of a given string P (length m) in a text T (length N),

• We use binary search against the suffix array of T to find the starting and end position of all occurrences of P.
• Now to speed up the search, we use LCP array, specifically a special version of the LCP array (LCP-LR below).

The issue with using standard binary search (without the LCP information) is that in each of the O(log N) comparisons needed to be made, we compare P to the current entry of the suffix array, which means a full string comparison of up to m characters. So the complexity is O(m*log N).

The LCP-LR array helps improve this to O(m+log N), in the following way:

At any point during the binary search algorithm, we consider, as usual, a range (L,...,R) of the suffix array and its central point M, and decide whether we continue our search in the left sub-range (L,...,M) or in the right sub-range (M,...,R). In order to make the decision, we compare P to the string at M. If P is identical to M, search is complete. But if not, we have already compared the first k characters of P and then decided whether P is lexicographically smaller or larger than M. Let's assume the outcome is that P is larger than M. So, in the next step, we consider (M,...,R) and a new central point M' in the middle:

       we know:          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', lcp(M,M').

We already know (from the previous step) that M itself has a prefix of k characters in common with P: lcp(P,M)=k. Now there are three possibilities:

• Case 1: k < lcp(M,M'), 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 > 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,...,M').
• Case 3: k == 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. 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. 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,...,R) will ever occur during the binary search: It always starts with (0,...,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...M...R) that can possibly play a role during binary search, and it suffices to precompute lcp(L,M) and lcp(M,R) for those N possible ranges. So that is 2*N distinct precomputed values, hence LCP-LR is O(N) in size.

Moreover, there is a straightforward recursive algorithm to compute the 2*N 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(Mlog 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.

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.

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 bytes, while the original output (text, suffix array, LCP array) only occupies bytes. Therefore, {{harvtxt|Manzini|2004}} created a refined version of the algorithm of {{harvtxt|Kasai|Lee|Arimura|Arikawa|2001}} (lcp9) and reduced the space occupancy to bytes. {{harvtxt|Kärkkäinen|Manzini|Puglisi|2009}} provide another refinement of Kasai's algorithm (-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.

Applications

As noted by {{harvtxt|Abouelhoda|Kurtz|Ohlebusch|2004}} 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.

Deciding if a pattern of length is a substring of a string of length takes time if only the suffix array is used. By additionally using the LCP information, this bound can be improved to time.{{sfn|Manber|Myers|1993}} {{harvtxt|Abouelhoda|Kurtz|Ohlebusch|2004}} show how to improve this running time even further to achieve optimal 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.{{sfn|Sadakane|2007}}{{sfn|Fischer|Mäkinen|Navarro|2009}} Furthermore, it can be used together with the suffix array to compute the Lempel-Ziv LZ77 factorization in time.{{sfn|Abouelhoda|Kurtz|Ohlebusch|2004}}{{sfn|Crochemore|Ilie|2008}}{{sfn|Crochemore|Ilie|Smyth|2008}}{{sfn|Chen|Puglisi|Smyth|2008}}

The longest repeated substring problem for a string of length can be solved in time using both the suffix array and the LCP array. It is sufficient to perform a linear scan through the LCP array in order to find its maximum value and the corresponding index where is stored. The longest substring that occurs at least twice is then given by .

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 and the LCP array of a string of length , its suffix tree can be constructed in 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 be the partial suffix tree for . Further let be the length of the concatenation of all path labels from the root of to node .

Start with , the tree consisting only of the root. To insert into , walk up the rightmost path beginning at the recently inserted leaf to the root, until the deepest node with is reached.

We need to distinguish two cases:

• : This means that the concatenation of the labels on the root-to- path equals the longest common prefix of suffixes and .
  In this case, insert as a new leaf of node and label the edge with . Thus the edge label consists of the remaining characters of suffix that are not already represented by the concatenation of the labels of the root-to- path.
  This creates the partial suffix tree .
• : This means that the concatenation of the labels on the root-to- path displays less characters than the longest common prefix of suffixes and and the missing characters are contained in the edge label of 's rightmost edge. Therefore, we have to split up that edge as follows:
  Let be the child of on 's rightmost path.

1. Delete the edge .
2. Add a new internal node and a new edge with label . The new label consists of the missing characters of the longest common prefix of and . Thus, the concatenation of the labels of the root-to- path now displays the longest common prefix of and .
3. Connect to the newly created internal node by an edge that is labeled . The new label consists of the remaining characters of the deleted edge that were not used as the label of edge .
4. Add as a new leaf and connect it to the new internal node by an edge that is labeled . Thus the edge label consists of the remaining characters of suffix that are not already represented by the concatenation of the labels of the root-to- path.
5. This creates the partial suffix tree .

A simple amortization argument shows that the running time of this algorithm is bounded by :

The nodes that are traversed in step by walking up the rightmost path of (apart from the last node ) are removed from the rightmost path, when is added to the tree as a new leaf. These nodes will never be traversed again for all subsequent steps . Therefore, at most nodes will be traversed in total.

LCP queries for arbitrary suffixes

The LCP array only contains the length of the longest common prefix of every pair of consecutive suffixes in the suffix array . However, with the help of the inverse suffix array (, i.e. the suffix that starts at position in is stored in position in ) and constant-time range minimum queries on , it is possible to determine the length of the longest common prefix of arbitrary suffixes in time.

Because of the lexicographic order of the suffix array, every common prefix of the suffixes and has to be a common prefix of all suffixes between 's position in the suffix array and 's position in the suffix array . Therefore, the length of the longest prefix that is shared by all of these suffixes is the minimum value in the interval . This value can be found in constant time if is preprocessed for range minimum queries.

Thus given a string of length and two arbitrary positions in the string with , the length of the longest common prefix of the suffixes and can be computed as follows: .

Notes

References

• {{cite journal| doi=10.1016/S1570-8667(03)00065-0 |ref=harv| title=Replacing suffix trees with enhanced suffix arrays| year=2004| last1=Abouelhoda| first1=Mohamed Ibrahim| last2=Kurtz| first2=Stefan| last3=Ohlebusch| first3=Enno| journal=Journal of Discrete Algorithms| volume=2| pages=53–86 }}
• {{cite journal| doi=10.1137/0222058 | ref=harv| title=Suffix Arrays: A New Method for On-Line String Searches| year=1993| last1=Manber| first1=Udi| last2=Myers| first2=Gene| journal=SIAM Journal on Computing| volume=22| issue=5| pages=935| citeseerx=10.1.1.105.6571}}
• {{cite conference |doi = 10.1007/3-540-48194-X_17 |ref=harv| conference = Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching | year = 2001 | last1 = Kasai | first1 = T. | last2 = Lee | first2 = G. | last3 = Arimura | first3 = H. | last4 = Arikawa | first4 = S. | last5 = Park | first5 = K. | title = Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications | series = Lecture Notes in Computer Science | volume = 2089 | pages = 181–192 | isbn = 978-3-540-42271-6

• {{cite conference| doi=10.1007/978-3-642-16321-0_34 |ref=harv| title=CST++| conference=String Processing and Information Retrieval| series=Lecture Notes in Computer Science| year=2010| last1=Ohlebusch| first1=Enno| last2=Fischer| first2=Johannes| last3=Gog| first3=Simon| isbn=978-3-642-16320-3| volume=6393| pages=322}}
• {{cite conference|ref=harv

• {{cite conference| doi = 10.1007/978-3-642-22300-6_32 |ref=harv| last1 = Fischer | first1 = Johannes | title = Inducing the LCP-Array | conference = Algorithms and Data Structures | series = Lecture Notes in Computer Science | volume = 6844 | pages = 374–385 | year = 2011 | isbn = 978-3-642-22299-3 | arxiv = 1101.3448 }}
• {{cite conference| doi=10.1007/978-3-540-27810-8_32 |ref=harv| title=Two Space Saving Tricks for Linear Time LCP Array Computation| conference=Algorithm Theory - SWAT 2004| series=Lecture Notes in Computer Science| year=2004| last1=Manzini| first1=Giovanni| isbn=978-3-540-22339-9| volume=3111| pages=372}}
• {{cite conference| doi=10.1007/978-3-642-02441-2_17 |ref=harv| title=Permuted Longest-Common-Prefix Array| conference=Combinatorial Pattern Matching| series=Lecture Notes in Computer Science| year=2009| last1=Kärkkäinen| first1=Juha| last2=Manzini| first2=Giovanni| last3=Puglisi| first3=Simon J.| isbn=978-3-642-02440-5| volume=5577| pages=181}}
• {{cite conference| doi=10.1007/978-3-540-92182-0_14 |ref=harv| title=Space-Time Tradeoffs for Longest-Common-Prefix Array Computation| conference=Algorithms and Computation| series=Lecture Notes in Computer Science| year=2008| last1=Puglisi| first1=Simon J.| last2=Turpin| first2=Andrew| isbn=978-3-540-92181-3| volume=5369| pages=124}}
• {{cite conference|ref=harv

• {{cite conference| doi=10.1109/DCC.2009.42 | ref=harv| title=Linear Suffix Array Construction by Almost Pure Induced-Sorting| conference=2009 Data Compression Conference| year=2009| last1=Nong| first1=Ge| last2=Zhang| first2=Sen| last3=Chan| first3=Wai Hong| isbn=978-0-7695-3592-0| pages=193}}
• {{cite conference | doi = 10.1007/978-3-540-74450-4_41 | ref=harv| last1 = Fischer | first1 = Johannes

• {{Cite journal | doi = 10.1007/s11786-007-0024-4 | ref= harv | last1 = Chen | first1 = G. | last2 = Puglisi | first2 = S. J. | last3 = Smyth | first3 = W. F. | title = Lempel–Ziv Factorization Using Less Time & Space | journal = Mathematics in Computer Science | volume = 1 | issue = 4 | pages = 605 | year = 2008 }}
• {{Cite journal | doi = 10.1016/j.ipl.2007.10.006 | ref=harv | last1 = Crochemore | first1 = M. | last2 = Ilie | first2 = L. | title = Computing Longest Previous Factor in linear time and applications | journal = Information Processing Letters | volume = 106 | issue = 2 | pages = 75 | year = 2008 | citeseerx=10.1.1.70.5720 }}
• {{Cite conference | doi = 10.1109/DCC.2008.36 | ref=harv | last1 = Crochemore | first1 = M. | last2 = Ilie | first2 = L. | last3 = Smyth | first3 = W. F. | title = A Simple Algorithm for Computing the Lempel Ziv Factorization | conference = Data Compression Conference (dcc 2008) | pages = 482 | year = 2008 | isbn = 978-0-7695-3121-2 }}
• {{Cite journal| doi = 10.1007/s00224-006-1198-x |ref=harv| last1 = Sadakane | first1 = K. | title = Compressed Suffix Trees with Full Functionality | journal = Theory of Computing Systems | volume = 41 | issue = 4 | pages = 589–607 | year = 2007 |citeseerx=10.1.1.224.4152}}
• {{Cite journal | doi = 10.1016/j.tcs.2009.09.012 | ref=harv | last1 = Fischer | first1 = Johannes | last2 = Mäkinen | first2 = Veli | last3 = Navarro | first3 = Gonzalo | title = Faster entropy-bounded compressed suffix trees | journal = Theoretical Computer Science | volume = 410 | issue = 51 | pages = 5354 | year = 2009 }}

External links

• [https://github.com/elventear/sais-lite-lcp Mirror of the ad-hoc-implementation of the code described in {{harvtxt|Fischer|2011}}]
• [https://github.com/simongog/sdsl/ SDSL: Succinct Data Structure Library - Provides various LCP array implementations, Range Minimum Query (RMQ) support structures and many more succinct data structures ]
• [https://github.com/carrotsearch/jsuffixarrays/blob/master/src/main/java/org/jsuffixarrays/Traversals.java Bottom-up suffix tree traversal emulated using suffix array and LCP array (Java)]
• [https://code.google.com/p/text-indexing/ Text-Indexing project] (linear-time construction of suffix trees, suffix arrays, LCP array and Burrows-Wheeler Transform)

• State Highway Route 157 (New Jersey)
• State Highway Route 158 (New Jersey)
• State Highway Route 159 (New Jersey)
• State Highway Route 15 (New Jersey)
• State Highway Route 161 (New Jersey)
• State Highway Route 162 (New Jersey)
• State Highway Route 163 (New Jersey)
• State Highway Route 165 (New Jersey)
• State Highway Route 166 (New Jersey)
• State Highway Route 168 (New Jersey)
• State Highway Route 169 (New Jersey)
• State Highway Route 171 (New Jersey)
• State Highway Route 172 (New Jersey)
• State Highway Route 173 (New Jersey)
• State Highway Route 175 (New Jersey)
• State Highway Route 179 (New Jersey)
• State Highway Route 17 (New Jersey)
• State Highway Route 181 (New Jersey)
• State Highway Route 182 (New Jersey)
• State Highway Route 183 (New Jersey)
• State Highway Route 184 (New Jersey)
• State Highway Route 185 (New Jersey)
• State Highway Route 187 (New Jersey)
• State Highway Route 18 (New Jersey)
• State Highway Route 18N (New Jersey)