LCP array: Difference between revisions

Revision as of 05:30, 11 February 2019

Revision as of 06:46, 9 August 2019

Line 27:

In [[computer science]], the '''longest common prefix array''' (LCP [[Array data structure|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'' := [<ttsamp>aab</ttsamp>, <ttsamp>ab</ttsamp>, <ttsamp>abaab</ttsamp>, <ttsamp>b</ttsamp>, <ttsamp>baab</ttsamp>] is a suffix array, the longest common prefix between ''A''[1] = <ttsamp>aab</ttsamp> and ''A''[2] = <ttsamp>ab</ttsamp> is <ttsamp><i>a</i></ttsamp> which has length 1, so ''H''[2] = 1 in the LCP array ''H''. Likewise, the LCP of ''A''[2] = <ttsamp>ab</ttsamp> and ''A''[3] = <ttsamp>abaab</ttsamp> is <ttsamp>ab</ttsamp>, so ''H''[3] = 2.

Augmenting the suffix array with the LCP array allows one to efficiently simulate top-down and bottom-up [[Tree traversal|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}}

Line 261:

==External links==

{{Commonscat}}

*[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)]