문자열 게임

시간 제한2초메모리 제한1024 MB

요약

주어진 문자열에서 겹치지 않게 두 번 이상 나타나는 부분 문자열 중 가장 긴 것의 길이를 구합니다.

난이도: 보통10점 중 6점
유형: 문자열 매칭, 이분 탐색, 정렬
정답자: 아직 제출이 없습니다

문제

알베르트 모이세예비치는 최근 iPad를 iOS 8.1로 업데이트했다. 별생각 없이 어제 나온 새 게임을 바로 설치했다.

게임 규칙은 간단하다. 소문자 라틴 문자로 이루어진 문자열 $s$ 가 주어진다. 제한 시간 안에 $s$ 에서 서로 겹치지 않는 출현 횟수가 가장 많은 부분 문자열을 찾아야 한다. 부분 문자열 $t$ 의 출현은 $l \le r$ 인 쌍 $(l, r)$ 로 정의하며, $s$ 의 $l$ 번째 문자부터 $r$ 번째 문자까지(양 끝 포함)가 $t$ 와 같아야 한다. 두 출현 $(l_1, r_1)$ 과 $(l_2, r_2)$ 는 구간 $[l_1, r_1]$ 과 $[l_2, r_2]$ 가 서로 겹치지 않을 때 겹치지 않는다고 한다.

게임에서는 찾은 부분 문자열의 길이만큼 점수를 얻는다. 알베르트 모이세예비치는 점수를 최대한 많이 얻고 싶어 하므로, 이 조건을 만족하는 부분 문자열 중 길이가 가장 긴 것을 찾아 달라고 부탁한다.

입력

첫 번째이자 유일한 줄에 문자열 $s$ 가 주어진다( $1 \le |s| \le 10^5$ ). 문자열은 소문자 라틴 문자로만 이루어져 있다.

출력

조건을 만족하는 부분 문자열의 최대 길이를 한 줄에 출력한다.

예제2

예제 1
입력
```
abacaba
```
예상 출력
```
1
```
예제 2
입력
```
abab
```
예상 출력
```
2
```