LCP array: Difference between revisions

Revision as of 20:12, 16 March 2015

Revision as of 09:30, 3 April 2015

Line 213:

Let <math>ST_{i}</math> be the partial suffix tree for <math>0\leq i \leq n</math>. Further let <math>d(v)</math> be the length of the concatenation of all path labels from the root of <math>ST_i</math> to node <math>v</math>.

[[File:Constructing the suffix tree of banana based on the suffix array and the LCP array - Case 1.pdf|thumb|400px|Case 1 (<math>d(v)=H[i+1]</math>): Suppose the suffixes <math>a$</math>, <math>ana$</math>, <math>anana$</math> and <math>banana$</math> of the string <math>S=banana$</math> are already added to the suffix tree. Then the suffix <math>na$</math> is added to the tree as shown in the picture. The ''rightmost'' path is highlighted in red.]]

Start with <math>S_0ST_0</math>, the tree consisting only of the root. To insert <math>A[i+1]</math> into <math>ST_i</math>, walk up the ''rightmost'' path beginning at the recently inserted leaf <math>A[i]</math> to the root, until the deepest node <math>v</math> with <math>d(v) \leq H[i+1]</math> is reached.

We need to distinguish two cases: