가장 긴 팰린드롬 부분 문자열

면접 대비

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

요약

길이가 최대 100,000인 소문자 문자열이 주어질 때, 가장 긴 팰린드롬 부분 문자열의 길이를 구한다.

문제

알파벳 소문자로만 이루어진 문자열 $S$ 가 주어진다. $S$ 의 부분 문자열 가운데 팰린드롬인 것 중에서 가장 긴 것의 길이를 구하는 프로그램을 작성하시오.

팰린드롬은 앞에서부터 읽으나 뒤에서부터 읽으나 같은 문자열이다. 부분 문자열은 $S$ 에서 연속한 구간을 잘라 낸 문자열이다.

첫째 줄에 알파벳 소문자로만 이루어진 문자열 $S$ 가 주어진다. $S$ 의 길이는 $100\,000$ 을 넘지 않는다.

첫째 줄에 $S$ 의 부분 문자열 중에서 팰린드롬이면서 길이가 가장 긴 것의 길이를 출력한다.