Skills101
← All coding problems

Longest Repeated Substring

hardStrings II+40 XPTime limit 3s

A DNA lab looks for the longest piece that occurs at least twice in a sequence. The two occurrences may overlap: in banana the answer is 3 (ana at positions 1 and 3). If no character repeats at all, the answer is 0.

Input: one line with a string of lowercase letters.

Output: the length of the longest substring that appears at least twice.

Constraints: 1 ≤ length ≤ 10⁵.

Think about it: two good routes. (1) Binary search on the length L — if some substring of length L repeats, so does one of length L − 1 — and check a length with rolling hashes in O(n). (2) Build a suffix automaton, count how many end positions each state has (push counts up the suffix links from longest to shortest), and take the largest len(v) among states seen at least twice. A suffix array's largest LCP also works.

Sample input 1

banana

Sample output 1

3

Sample input 2

abcd

Sample output 2

0

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.