LCP array

In computer science, the longest common prefix array (LCP array) is an auxiliary data structure to the suffix array, which stores the length of the longest common prefix between every pair of lexicographically consecutive suffixes in the suffix array.

Augmenting the suffix array with the LCP array allows to efficiently simulate top-down and bottom-up traversals of the suffix tree (Kasai et al. 2001), speeds up pattern matching on the suffix array and is a prerequisite for compressed suffix trees(Ohlebusch, Fischer, and Gog 2010).

History

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

Definition

Let SA be the suffix array of the text T=$t_{1},t_{2},...t_{n}$ and let lcp(v,w) denote the length of the longest common prefix between two strings v and w. Let further denote T[i,j] the substring of T ranging from i to j.

Then the LCP array H[1,n] is an integer array of size n such that H[1] is undefined and H[i]=lcp(T[SA[i-1],n],T[SA[i],n]) for every $1<i\leq n$. Thus H[i] stores the length of longest common prefix of the lexicographic (i-1)'st and ith smallest suffix of T.

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 (Manber and Myers 1993)(Kärkkäinen and Sanders 2003)(Fischer 2011)
• algorithms that compute the LCP array from the already constructed suffix array (Kasai et al. 2001)(Manzini 2004)(Kärkkäinen, Manzini, and Puglisi 2009)(Puglisi and Turpin 2008)(Gog and Ohlebusch 2011)

Currently, the 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 (Nong, Zhang, and Chan 2009)

References

• Abouelhoda, Mohamed Ibrahim; Ohlebusch, Enno; Ohlebusch, Enno (2004), "Replacing suffix trees with enhanced suffix arrays", J. of Discrete Algorithms, 2 (1): 53–86, doi:10.1016/S1570-8667(03)00065-0, retrieved 2012-08-28
• Manber, U.; Myers, G. (1993), </div "Suffix Arrays: A New Method for On-Line String Searches", SIAM Journal on Computing, 22 (5): 935–948, doi:10.1137/0222058, retrieved 2012-08-28
• Kasai, Toru; Lee, Gunho; Arimura, Hiroki; Arikawa, Setsuo; Park, Kunsoo} (2001), "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications", Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching: 181–192, ISBN 3-540-42271-4, retrieved 2012-08-28
• Ohlebusch, Enno; Fischer, Johannes; Gog, Simon (2010), "CST++", String Processing and Information Retrieval - 17th International Symposium, SPIRE 2010, Los Cabos, Mexico, October 11-13, 2010. Proceedings, 6393: 322–333, doi:http://dx.doi.org/10.1007/978-3-642-16321-0_34 {{citation}}: Check |doi= value (help); External link in |doi= (help)
• Kärkkäinen, Juha; Sanders, Peter; Burkhardt, Stefan (2006). "Linear work suffix array construction". Journal of the ACM. 53 (6): 918–936. doi:10.1145/1217856.1217858. ISSN 0004-5411.
• A bot will complete this citation soon. Click here to jump the queue arXiv:1101.3448v1.
• Manzini, Giovanni (2004), "Two space saving tricks for linear time LCP computation", Proc. SWAT. Volume 3111 of Lecture Notes in Computer Science, 3111: 372–383
• Gog, Simon; Ohlebusch, Enno (2011), "Fast and Lightweight LCP-Array Construction Algorithms" (PDF), Proceedings of the Workshop on Algorithm Engineering and Experiments, ALENEX 2011: 25–34, retrieved 2012-08-28