삭제

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

요약

문자열에서 구간 w[a..b]를 지운 뒤 남은 문자열에 그 구간이 다시 나타나는 가장 긴 구간의 길이를 구합니다.

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

문제

영어 소문자로 이루어진 길이 n의 문자열 w가 주어진다. 1 ≤ a ≤ b ≤ n을 만족하는 자연수 a, b에 대해, w의 a번째 문자부터 b번째 문자까지를 이어 붙인 부분 문자열을 $w_{a,b}$ 라고 한다. 또한 w에서 a번째 문자부터 b번째 문자까지를 모두 지우고 남은 문자열을 $o_{a,b}$ 라고 한다. $o_{a,b}$ 가 부분 문자열로 $w_{a,b}$ 를 포함하는 $w_{a,b}$ 중에서 가장 긴 것의 길이를 구하라.

입력

첫 줄에 영어 소문자로 이루어진 문자열 w가 주어진다.

출력

가능한 가장 큰 길이를 출력한다.

힌트

두 번째 예제의 설명: bbcdbcb*bcbad*adda → bbcd*bcbad*da

예제2

예제 1
입력
```
abcxyzabc
```
예상 출력
```
3
```
예제 2
입력
```
bbcdbcbbcbadadda
```
예상 출력
```
5
```