Longest Repeated Substring

Compression tools and plagiarism checkers both hunt for text that occurs more than once. Write longest_repeat(text) that returns the longest substring (a run of consecutive characters) that appears in text at least twice. The two appearances may overlap: in "aaaa" the answer is "aaa".

If several different substrings have that longest length, return the one whose first appearance starts earliest in text. If no character appears twice, return the empty string.

Examples

longest_repeat('banana')        # returns 'ana'
longest_repeat('abcd')          # returns ''
longest_repeat('xyzabcxyzabd')  # returns 'xyzab'
longest_repeat('xyabqabxy')     # returns 'xy'

In "banana" the two copies of "ana" share the middle "a". In the last example "xy" and "ab" both appear twice, and "xy" first appears earlier.

Constraints

• 0 <= len(text) <= 10,000
• text contains only lowercase English letters.
• Comparing every pair of positions is far too slow for the longest texts.