given the suffix array formula_1 and the lcp array formula_18 of a string formula_2 of length formula_51, its suffix tree formula_52 can be constructed in formula_25 time based on the following idea: start with the partial suffix tree for the lexicographically smallest suffix and repeatedly insert the other suffixes in the order given by the suffix array.