Content deleted Content added
m Add category |
|||
Line 238:
== Constructing the lcp-interval ==
For a suffix array of S, the lcp-interval associated with the corresponding node of suffix tree of S can be defined as:
{{quote|1=
▲''Interval [i,..j], 0 ≤ i ≤ j ≤ n is an lcp-interval of lcp-value, if''
▲''1. lcptab[i] < l,''
}}
▲''2. lcptab[k] ≥ l for all i + 1 ≤ k ≤ j,''
▲''3. lcptab[k] = l for some i + 1 ≤ k ≤ j if i ≠ j and l = n − i + 1 if i = j,''
▲''4. lcptab[j + 1] < l.''
The length of the longest common prefix of pos[i − 1] and pos[i] is stored in lcp[i],where 2 ≤ i ≤ n. The lcp-interval portrays the same parent-child relationship as that among the associated nodes in the suffix tree of S.This shows that if the corresponding node of [i..j] is a child of the corresponding node of [k..l], a lcp-interval [i..j] is a child interval of another lcp-interval [k..l]. If [k..l] is a child interval of [i..j], a lcp-interval [i..j] is the parent interval of a lcp-interval [k..l].
| |||