Editing Suffix array (section)

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

# lcptab[i] < l,
# lcptab[k] ≥ l for all i + 1 ≤ k ≤ j,
# lcptab[k] = l for some i + 1 ≤ k ≤ j if i ≠ j and l = n − i + 1 if i = j, 
# 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].