Bipalíndromos P12466

Un palíndromo es una palabra que se escribe igual del derecho que del revés, como por ejemplo Y, EE, ALA, ANNA, ROTOR o AAAAAA. En este problema te pedimos que, dada una palabra, calcules cuántos palíndromos distintos contiene. Por ejemplo, ROTORO contiene 6 palíndromos de longitud 1, 2 palíndromos de longitud 3, y 1 palíndromo de longitud 5, por lo que la respuesta final debería ser 9.

Y por si este problema fuera “muy fácil” para ti, te daremos más puntos si, además de contar el número de palíndromos de la palabra, eres capaz de contar el número de bipalíndromos (pares de palíndromos en la palabra, el primero de ellos apareciendo antes que el segundo, y sin que ocupen las mismas letras). Por ejemplo, ROTORO tiene exactamente 22: (R)(O)TORO, (R)O(T)ORO, (R)OTO(R)O, (R)OT(ORO), R(OTO)(R)O, etc.

Entrada

Una línea con una palabra de no más de 5000 letras mayúsculas. Opcionalmente, una segunda línea con el texto BIPALINDROMES.

Salida

Escribe una línea con el número de palíndromos que contiene la palabra dada. Si la entrada contiene una segunda línea con el texto BIPALINDROMES, escribe una segunda línea de salida con el número de bipalíndromos en la palabra dada.

Puntuación

• TestA:   Palíndromos de entradas con 5 o menos letras.

• TestB:   Palíndromos de entradas con 100 o menos letras.

• TestC:   Palíndromos de entradas con 5000 o menos letras.

• TestD:   Palíndromos y bipalíndromos de entradas con 5000 o menos letras.