|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|10 초||128 MB||62||26||24||40.000%|
A partition of a string s is a set of one or more non-overlapping non-empty substrings of s (call them a1, a2, a3, . . . , ad), such that s is their concatenation: s = a1 +a2 +a3 +. . .+ad. We call these substrings "chunks" and define the length of such a partition to be the number of chunks, d.
We can represent the partition of a string by writing each chunk in parentheses. For example, the string "
decode" can be partitioned as
(de)(code) or a number of other ways.
A partition is palindromic if its chunks form a palindrome when we consider each chunk as an atomic unit. For example, the only palindromic partitions of "
(decode). This also illustrates that every word has a trivial palindromic partition of length one.
Your task is to compute the maximal possible number of chunks in palindromic partition.
The input starts with the number of test cases t in the first line. The following t lines describe individual test cases consisting of a single word s, containing only lowercase letters of the English alphabet. There are no spaces in the input.
Let us denote the length of the input string s with n.
For every testcase output a single number: the length of the longest palindromic partition of the input word s.
4 bonobo deleted racecar racecars
3 5 7 1