팰린팰린드롬

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

요약

문자열을 앞뒤 순서가 같은 블록들로 나눌 때, 가장 큰 블록의 길이를 최소로 하는 값을 구한다.

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

문제

왼쪽에서 오른쪽으로 읽은 결과와 오른쪽에서 왼쪽으로 읽은 결과가 동일한 문자열을 팰린드롬이라고 한다. 예를 들어, ABBA는 팰린드롬이고, PICKLE은 팰린드롬이 아니다.

민기는 어느 날 "꼬들꼬들한 꼬들꼬들"이라는 문자열을 봤는데, 공백을 제거하고 "꼬들"을 묶어서 하나로 생각하면 팰린드롬이 된다는 생각을 했다. 이것이 너무 감명 깊었던 민기는 이러한 분할을 팰린팰린분할이라고 정의하기로 결심했다. 구체적인 정의는 다음과 같다:

문자열 $S$ 가 있을 때, $S$ 를 비어 있지 않은 연속한 부분문자열 $K$ 개로 분할할 수 있다. 이때, 만약 $1\leq i \leq K$ 인 모든 $i$ 에 대해 $i$ 번째 부분문자열과 $K - i + 1$ 번째 부분문자열이 같다면, 그 분할 방법을 팰린팰린분할이라고 하자. 그리고, 분할된 $K$ 개의 부분문자열들의 길이의 최댓값을 팰린팰린분할의 크기라고 정의하자. 문자열 $S$ 의 모든 팰린팰린분할에 대하여, 팰린팰린분할의 크기의 최솟값이 $n$ 일 때, $S$ 를 $n$ -팰린팰린드롬이라고 정의한다.

예를 들어, ABCDABC는 (ABC)(D)(ABC)와 같이 분할할 수 있고, 이때 부분문자열의 길이의 최댓값은 $3$ 이며, 크기가 $2$ 이하인 팰린팰린분할은 존재하지 않는다. 따라서 ABCDABC는 $3$ -팰린팰린드롬이다.

민기의 정의를 토대로, 주어진 문자열이 $n$ -팰린팰린드롬일 때, $n$ 의 값을 구해보자.

입력

문자열 $S$ 가 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있다. ( $1 \leq |S| \leq 500\\,000$ )

출력

문자열 $S$ 가 $n$ -팰린팰린드롬일 때, $n$ 의 값을 출력하라.

힌트

$|S|$ 는 문자열 $S$ 의 길이를 의미한다.

예제3

예제 1
입력
```
ABCAB
```
예상 출력
```
2
```
예제 2
입력
```
IAMCODER
```
예상 출력
```
8
```
예제 3
입력
```
EERTREE
```
예상 출력
```
1
```