#216HardStrings· Binary Search with Rolling Hash

Longest Repeated Log Segment

A monitoring service compresses its event log into one string of lowercase letters, one letter per event type. An engineer suspects the system is stuck in a loop and wants to know the longest sequence of events that happened at least twice in the log. The two occurrences may overlap each other: in `"aaaa"` the segment `"aaa"` occurs at positions 0 and 1. Return the length of the longest segment (contiguous substring) that appears at least twice, or `0` if every segment appears only once.

Input format

`log`: a string of lowercase English letters.

Output format

A single integer: the length of the longest substring that occurs at least twice.

Examples

Input: log = "banana"

Output: 3

The segment "ana" occurs at positions 1 and 3 (overlapping on the middle "a"). No segment of length 4 repeats.

Input: log = "abcdef"

Output: 0

All letters are different, so no segment appears twice and the answer is 0.

Input: log = "aaaaa"

Output: 4

"aaaa" starts at positions 0 and 1, so overlapping repeats count and the answer is 4.

Constraints

1 <= log.length <= 30000
`log` consists of lowercase English letters.

#string-hashing
#rolling-hash
#binary-search
#strings