한 고문서 복원가가 손상된 문자열 하나를 들여다보고 있다. 그는 이 문자열 안에서 앞에서 읽으나 뒤에서 읽으나 똑같은, 즉 회문(palindrome)을 이루는 가장 긴 연속된 구간을 찾아 그 길이를 기록하려 한다.

문자열 \(S\) 가 주어질 때, \(S\) 의 부분문자열(연속한 구간) 중 회문인 것의 최대 길이를 구하는 프로그램을 작성하라.

예를 들어 \(S = \) babad 라면, 회문인 부분문자열로는 b, a, bab, aba 등이 있고 그중 가장 긴 것은 bab (또는 aba)으로 길이가 \(3\) 이다. \(S = \) cbbd 라면 가장 긴 회문 부분문자열은 bb 로 길이가 \(2\) 이다.

참고로 문자 하나로 이루어진 부분문자열은 언제나 회문이므로, 답은 항상 \(1\) 이상이다.

\(1 \le |S| \le 200{,}000\)

\(S\) 는 영문 소문자(a–z)로만 이루어져 있다.

첫째 줄에 영문 소문자로만 이루어진 문자열 \(S\) 가 주어진다.

\(S\) 의 길이는 \(1\) 이상 \(200{,}000\) 이하이다.

\(S\) 의 부분문자열 중 회문인 것의 최대 길이를 한 줄에 출력한다.

riseoj 작성

출처 Original