시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 128 MB | 167 | 69 | 64 | 48.120% |
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 (d)(ec)(ode)
or (d)(e)(c)(od)(e)
or (decod)(e)
or (decode)
or (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
" are (de)(co)(de)
and (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.
For every testcase output a single number: the length of the longest palindromic partition of the input word s.
Let us denote the length of the input string s with n.
번호 | 배점 | 제한 |
---|---|---|
1 | 15 | n ≤ 30 |
2 | 20 | n ≤ 300 |
3 | 25 | n ≤ 10 000 |
4 | 40 | No additional constraints |
4 bonobo deleted racecar racecars
3 5 7 1