CEOI '17 P5 - Palindromic Partitions

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 4.5s
Memory limit: 128M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

A partition of a string s is a set of one or more non-overlapping non-empty substrings of s (call them a_1, a_2, a_3, \dots , a_d), such that s is their concatenation: s = a_1 +a_2 +a_3 + \dots +a_d. 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.

Input

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.

Output

For every testcase output a single number: the length of the longest palindromic partition of the input word s.

Constraints

Let us denote the length of the input string s with n.

  • 1 \le t \le 10
  • 1 \le n \le 10^6
Subtask 1 (15%)
  • n \le 30
Subtask 2 (20%)
  • n \le 300
Subtask 3 (25%)
  • n \le 10\,000
Subtask 4 (40%)
  • no additional constraints

Sample Input 1

4
bonobo
deleted
racecar
racecars

Sample Output 1

3
5
7
1

Comments

There are no comments at the moment.