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

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

보통7문자열문자열 매칭동적 계획법투 포인터면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제5

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

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

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

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