Construct a Suffix Tree from a Suffix Array solved by 140

SuffixTree(Text) can be constructed in linear time from SuffixArray(Text) by using the longest common prefix (LCP) array of Text, LCP(Text), which stores the length of the longest common prefix shared by consecutive lexicographically ordered suffixes of Text. For example, LCP("panamabananas$") is (0, 0, 1, 1, 3, 3, 1, 0, 0, 0, 2, 2, 0, 0).

Suffix Tree Construction from Suffix Array Problem

Construct a suffix tree from the suffix array and LCP array of a string.

Given: A string Text, SuffixArray(Text), and LCP(Text).

Return: The strings labeling the edges of SuffixTree(Text). (You may return these strings in any order.)

Sample Dataset

GTAGT$
5, 2, 3, 0, 4, 1
0, 0, 0, 2, 0, 1

Sample Output

$
T
AGT$
$
AGT$
GT
$
AGT$

Extra Datasets

Click for debug datasets