16301번 - Isomorphic Inversion 다국어

문제

Let s be a given string of up to 10⁶ 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 s₀, s₁, . . . , s_k−1 form a palindrome if s_i = s_k−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 10⁶ digits.

출력

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

제한

힌트