Partición Palíndrome
Una partición de una cadena s es un conjunto de uno o mas subcadenas no vacÍas y que no se solapan (la nombramos como ), tal que s es su concatenación: . Llamarenos a estas subcadenas “pedazos” y definimos como longitud de la particion al numero de “pedazos”.
Podemos representar la partición de una cadena encribiendo cada pedazo entre paréntesis. Por ejemplo, la cadena “decode” puede ser particionada como: (d)(ec)(ode) or (d)(e)(c)(od)(e) o (decod)(e) o (decode) o (de)(code)
Una partición es palindrome si sus “pedazos” forman un palindrome cuando consideramos cada pedazo como una unidad atómica. Por ejemplo, las particiones palindrome de "decode" son: (de)(co)(de) y (decode) . Esto tambien ilustra que cada palabra tiene una partición palindrome trivial de longitud 1.
Tu tarea es calcular el número máximo posible de “pedazos” en una partición palindrome.
Entrada
La entrada comienza con el número de casos de prueba en la primera línea. Las siguientes líneas describen los casos de pruebas individuales consistentes de una palabra simple , conteniendo solamente letras minúsculas del alfabeto inglés. No hay espacios en la entrada.
Salida
Para cada caso de prueba escribir un número simple: la longitud de la partición palindrome más larga de la palabra entrada.
Ejemplo de Entrada
4
bonobo
deleted
racecar
racecars
Ejemplo de Salida
3
5
7
1
Subtareas
Subtarea 1 (15 puntos)
Subtarea 2 (20 puntos)
Subtarea 3 (25 puntos)
Subtarea 4 (40 puntos) sin restricciones adicionales.
Comments