시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB145563235.556%

문제

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.

예제 입력 1

652526

예제 출력 1

4

예제 입력 2

12121131221

예제 출력 2

7

예제 입력 3

123456789

예제 출력 3

1

예제 입력 4

132594414896459441321

예제 출력 4

9

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2018 Preliminaries I번

  • 문제를 만든 사람: Ragnar Groot Koerkamp