String Game

Time limit2sMemory limit1024 MB

Summary

Given a string, find the longest substring that has at least two non-overlapping occurrences in the string and print its length.

Level: Medium6 of 10
Topics: String matching, Binary search, Sorting
Solved: No attempts yet

Problem

Albert Moiseevich recently updated his iPad to iOS 8.1. Without much thought, he installed a new game that came out only yesterday.

The game is simple. You are given a string $s$ made of lowercase Latin letters. Within the time limit, the player must find a substring that has the maximum number of non-overlapping occurrences in $s$ . An occurrence of a substring $t$ in $s$ is a pair $(l, r)$ with $l \le r$ such that the part of $s$ from position $l$ to position $r$ , inclusive, equals $t$ . Two occurrences $(l_1, r_1)$ and $(l_2, r_2)$ are non-overlapping if the segments $[l_1, r_1]$ and $[l_2, r_2]$ do not intersect.

The player earns points equal to the length of the found substring. Albert Moiseevich wants to score as many points as possible, so he asks you to find the substring of maximum length that satisfies this condition.

Input

The first and only line contains the string $s$ ( $1 \le |s| \le 10^5$ ), made only of lowercase Latin letters.

Output

Print one line with the maximum length of a substring that satisfies the condition.

Examples2

Example 1
Input
```
abacaba
```
Expected output
```
1
```
Example 2
Input
```
abab
```
Expected output
```
2
```