cho.sh

Isomorphic Inversion

길이 10^6 이하의 숫자 문자열이 주어질 때, 문자열을 k개의 연속한 조각으로 나누어 그 조각들의 나열이 앞뒤로 같은 팰린드롭이 되도록 하는 최대 k를 구한다.

어려움8문자열그리디해시맵투 포인터아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

Let s be a given string of up to 106 digits. Find the maximal k for which it is possible to partition s into k consecutive contiguous substrings, such that the k parts form a palindrome. More precisely, we say that strings s0, s1, . . . , sk−1 form a palindrome if si = sk−1−i for all 0 ≤ i < k.

In the first sample case, we can split the string 652526 into 4 parts as 6|52|52|6, and these parts together form a palindrome. It turns out that it is impossible to split this input into more than 4 parts while still making sure the parts form a palindrome.

입력

  • A nonempty string of up to 106 digits.

출력

  • Print the maximal value of k on a single line.