Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
LCP array
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the longest common prefix array (LCP <a href="/facts/Array_data_structure/BKGvF8AM">array</a>) is an auxiliary <a href="/facts/Data_structure/yNsNvL1I">data structure</a> to the <a href="/facts/Suffix_array/Q87p7bYH">suffix array</a>. It stores the lengths of the longest common prefixes (LCPs) between all pairs of consecutive suffixes in a sorted suffix array. </p><p>For example, if <i>A</i> := [aab, ab, abaab, b, baab] is a suffix array, the longest common prefix between <i>A</i>[1] = aab and <i>A</i>[2] = ab is <i>a</i> which has length 1, so <i>H</i>[2] = 1 in the LCP array <i>H</i>. Likewise, the LCP of <i>A</i>[2] = ab and <i>A</i>[3] = abaab is ab, so <i>H</i>[3] = 2. </p><p>Augmenting the suffix array with the LCP array allows one to efficiently simulate top-down and bottom-up <a href="/facts/Tree_traversal/Dkch34pz">traversals</a> of the <a href="/facts/Suffix_tree/pdQdCxbe">suffix tree</a>, speeds up pattern matching on the suffix array and is a prerequisite for compressed suffix trees. </p>