the longest repeated substring problem for a string formula_7 of length formula_11 can be solved in formula_42 time using both the suffix array formula_1 and the lcp array. it is sufficient to perform a linear scan through the lcp array in order to find its maximum value formula_44 and the corresponding index formula_8 where formula_44 is stored. the longest substring that occurs at least twice is then given by formula_47.