LCP array: Difference between revisions

Revision as of 20:05, 23 June 2015

Revision as of 20:41, 13 August 2015

Line 25:

|}

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 between pairs of consecutive [[Suffix (computer scienceLCPs)|suffixes]] inbetween theall sorted suffix array. In other words, it is the lengthpairs of prefix that is common between the two consecutive suffixes in a sorted suffix array.

For example, if ''A'' := [<tt>aab</tt>, <tt>ab</tt>, <tt>abaab</tt>, <tt>b</tt>, <tt>baab</tt>] is a suffix array, the longest common prefix between ''A''[1] = <tt>aab</tt> and ''A''[2] = <tt>ab</tt> is <tt>a</tt> which has length 1, so ''H''[2] = 1 in the LCP array ''H''. Likewise, the LCP of ''A''[2] = <tt>ab</tt> and ''A''[3] = <tt>abaab</tt> is <tt>ab</tt>, so ''H''[3] = 2.

Example:

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}}

LCP of '''a''' and '''a'''abba is 1.

LCP of '''ab'''aabba and '''ab'''ba is 2.

Augmenting the suffix array with the LCP array allows 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}}

== History ==