LCP array

\n| Space\n| <math>\\mathcal{O}(n)</math>\n| <math>\\mathcal{O}(n)</math>\n<!-- -->\n| Construction\n| <math>\\mathcal{O}(n)</math>\n| <math>\\mathcal{O}(n)</math>\n}}"}},"i":0}}]}'>

LCP array
Type	Array
Invented by	Manber & Myers (1993)
Time complexity and space complexity in big O notation
Average Worst case Space 𝒪(n) A be the suffix array of the string $ is a sentinel letter that is unique and lexicographically smaller than any other character. Let i to ith smallest suffix of v and n such that 1<i≤n. Thus S=banana$: scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>i 1 2 3 4 5 6 7 scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>S[i] b a n a n a $ and its corresponding sorted suffix array A[i] 7 6 4 2 1 5 3 Suffix array with suffixes written out underneath vertically: scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>i 1 2 3 4 5 6 7 scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>A[i] 7 6 4 2 1 5 3 scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>S[A[i], n][1] $ a a a b n n scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>S[A[i], n][2] $ n n a a a scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>S[A[i], n][3] a a n $ n scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>S[A[i], n][4] $ n a a scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>S[A[i], n][5] a n $ scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>S[A[i], n][6] $ a scope=\"row\" style=\"text-align:left;\"</span>"},{"html":""}]]}'>S[A[i], n][7] $ Then the LCP array H[i]		undefined	0	1	3	0	0	2

So, for example, A[3]=S[4,7]=ana$ and O(nlog⁡n) time. Kärkkäinen & Sanders (2003) show that it is also possible to modify their 13n bytes, while the original output (text, suffix array, LCP array) only occupies As of 2012, the currently fastest linear-time LCP array construction algorithm is due to Fischer (2011), which in turn is based on one of the fastest suffix array construction algorithms (SA-IS) by Nong, Zhang & Chan (2009). Fischer & Kurpicz (2017) based on Yuta Mori's DivSufSort is even faster.

As noted by 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.

Kasai et al. (2001) show how to simulate a bottom-up traversal of the suffix tree using only the suffix array and LCP array. Abouelhoda, Kurtz & Ohlebusch (2004) 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. Fischer & Heun (2007) 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.

Deciding if a pattern S of length O(m+log⁡n) time. Abouelhoda, Kurtz & Ohlebusch (2004) show how to improve this running time even further to achieve optimal S of length A and the LCP array. It is sufficient to perform a linear scan through the LCP array in order to find its maximum value vmax is stored. The longest substring that occurs at least twice is then given by

In order to find the number of occurrences of a given string T (length 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(m+log⁡N), in the following way:

At any point during the binary search algorithm, we consider, as usual, a range (L,…,M) or in the right sub-range M. If k characters of M. Let's assume the outcome is that (M,…,R) and a new central point M and M itself has a prefix of lcp(P,M)=k. Now there are three possibilities:

• Case 1: k>lcp(M,M′), i.e. M has in common with M′, the common prefix would be smaller than P, so, without actually making the comparison, we continue in the left half P to P is compared to any character of the text more than once (for details see ). The total number of character comparisons is bounded by 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. M and (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 lcp(M,R) for those O(N) in size.

  Moreover, there is a straightforward recursive algorithm to compute the O(N) time and O(M+log⁡N).

• We can use two binary searches to determine the left and right end of the match range for H of a string ST can be constructed in 0≤i≤n. Further let v.
  Case 1 (ana$, S=banana$ are already added to the suffix tree. Then the suffix A[i+1] into v with v path equals the longest common prefix of suffixes A[i+1] as a new leaf (v,x) with v path.
  This creates the partial suffix tree nana$, the edge to the previously inserted suffix nana$. The edges connecting the two leaves are labeled with the remaining suffix characters that are not part of the prefix.
• A[i] and STi's rightmost path.

1. Delete the edge (v,y) with label A[i+1]. Thus, the concatenation of the labels of the root-to-A[i+1].
2. Connect (y,w) that is labeled (v,y).
3. Add y by an edge A[i+1] that are not already represented by the concatenation of the labels of the root-to-O(n):

   The nodes that are traversed in step v) are removed from the rightmost path, when 2n nodes will be traversed in total.

   LCP queries for arbitrary suffixes

   edit

   The LCP array A−1 (j in A) and constant-time range minimum queries on S[i,n] and H is preprocessed for range minimum queries.

   Thus given a string i,j in the string S[i,n] and

   1. ↑ Kasai et al. 2001.
   2. 1 2 3 Abouelhoda, Kurtz & Ohlebusch 2004.
   3. 1 2 3 4 5 Manber & Myers 1993.
   4. ↑ Ohlebusch, Fischer & Gog 2010.
   5. ↑ Sadakane 2007.
   6. ↑ Fischer, Mäkinen & Navarro 2009.
   7. ↑ Crochemore & Ilie 2008.
   8. ↑ Crochemore, Ilie & Smyth 2008.
   9. ↑ Chen, Puglisi & Smyth 2008.