Longest Repeated Substring

Given a string \(S\) consisting of lowercase English letters, your task is to find the longest substring that appears at least twice in \(S\). A substring is defined as a contiguous sequence of characters within \(S\). If no such substring exists, output an empty string.

The problem can be solved efficiently using a binary search combined with a hashing technique. In each step, you check whether there exists a substring of a given length that occurs at least twice. If such a substring is found, try for a longer length; otherwise, try a shorter length.

For example, when \(S = \texttt{abcabcbb}\), the longest repeated substring is \(\texttt{abc}\). Other examples include:

• \(\texttt{banana} \rightarrow \texttt{ana}\)
• \(\texttt{ababa} \rightarrow \texttt{aba}\)
• \(\texttt{aaaaa} \rightarrow \texttt{aaaa}\)

inputFormat

The input consists of a single line containing the string \(S\) (only lowercase English letters).

outputFormat

Output the longest substring that occurs at least twice in \(S\). If no such substring exists, output an empty string.

abcabcbb

abc