The longest repeated piece

Return the longest piece (a run of neighbouring letters) of s that occurs at two or more places. The two copies may overlap. If several different pieces have that length, return the one whose first occurrence is earliest in s: in "cdqcdabqab" both "cd" and "ab" repeat, and "cd" is seen first. If no piece repeats at all, return "".

longest_repeat("banana")       # "ana"
longest_repeat("aaaa")         # "aaa"
longest_repeat("cdqcdabqab")   # "cd"
longest_repeat("abcd")         # ""

The string has lower-case letters. If you use a rolling hash, use a large prime modulus such as (1 << 61) - 1, and compare the letters when two hashes are equal: one test is built to make weak hashes give the same value for different pieces.

Limits

• Up to 100,000 letters. The big tests have 4 to 5 seconds each.
• The answer can be almost as long as the string, so building a slice for every piece of every length you try is too slow.