Longest Repeated Substring

Given a non-empty string s, find the longest substring that appears at least twice in s. The occurrences of the substring may overlap. If there are multiple substrings of the same maximum length, you may output any one of them. If no substring appears twice, output an empty string.

Note: A substring is a contiguous sequence of characters within the string.

For example:

• For s = "banana", the answer is ana.
• For s = "abcd", no substring appears twice so the answer is an empty string.

The solution should read the input from standard input and write the output to standard output.

inputFormat

The input consists of a single line containing a non-empty string s composed of lowercase English letters.

outputFormat

Output the longest substring that appears at least twice in s. If there is no such substring, output an empty string.

banana

ana