Longest Repeating Substring

Given a string s, your task is to find the longest substring that appears at least twice in s. If there are multiple substrings of maximum length that repeat, you may return any one of them. If no such substring exists, output an empty string.

Note: The substring occurrences may overlap. For example, in the string ababab, the substring abab appears twice (from indices 0 to 3 and 2 to 5).

The solution should be efficient. One approach is to use binary search on the length of the substring combined with a hash-based search. In formulas, you can see the search space as the interval \( [1, n] \) where \( n \) is the length of the string.

inputFormat

The input consists of a single line containing the string s.

Constraints: 1 \( \leq |s| \leq \) 10000. The string consists of lowercase English letters.

outputFormat

Output a single line containing the longest substring that appears at least twice in s. If no such substring exists, output an empty string.

banana

ana