7261 : 가장 긴 팰린드롬
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
주어진 문자열의 부분 문자열 중 가장 긴 팰린드롬(회문)의 길이를 구하십시오.
이분탐색으로 팰린드롬의 길이를 탐색하고, 해당 길이의 팰린드롬이 존재하는지 확인합니다.
[제약 조건]
• 문자열은 영문 소문자로만 구성됩니다.
이분탐색으로 팰린드롬의 길이를 탐색하고, 해당 길이의 팰린드롬이 존재하는지 확인합니다.
[제약 조건]
• 문자열은 영문 소문자로만 구성됩니다.
입력 설명
첫째 줄에 영문 소문자로 이루어진 문자열이 주어집니다. (길이 $\le 100{,}000$)
출력 설명
부분 문자열 중 가장 긴 팰린드롬의 길이를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
racecar
출력 예시
COPY
복사되었습니다!
복사되었습니다!
7도움
홀수 길이와 짝수 길이에 대해 각각 이분탐색을 적용하거나, 중심 확장법($O(N^2)$) 또는 Manacher 알고리즘($O(N)$)을 사용합니다.