Algorithmes et Structures de Données

Palindromes

Les chaînes de caractères qui se lisent de la même façon de gauche à droite et de droite à gauche sont appelées palindromes (par exemple radar, madam ou racecar).

Étant donné une chaîne de caractères s, on vous demande de déterminer le nombre de façons distinctes d’obtenir un palindrome à partir de s en retirant certains caractères. Il est tout à fait possible de ne retirer aucun caractère pour obtenir un palindrome. L’ordre dans lequel on enlève les caractères n’a pas d’importance.

Entrée

L’entrée contient la chaîne s (1 ≤ |s| ≤ 60), composée de lettres latines majuscules.

Sortie

Le programme doit afficher le nombre de façons différentes d’obtenir un palindrome à partir de s.

Exemples

Entrée

Sortie

BAOBAB

22

Explication

  1. BAOBAB

  2. BAOBAB

  3. BAOBAB

  4. BAOBAB

  5. BAOBAB

  6. BAOBAB

  7. BAOBAB

  8. BAOBAB

  9. BAOBAB

  10. BAOBAB

  11. BAOBAB

  12. BAOBAB

  13. BAOBAB

  14. BAOBAB

  15. BAOBAB

  16. BAOBAB

  17. BAOBAB

  18. BAOBAB

  19. BAOBAB

  20. BAOBAB

  21. BAOBAB

  22. BAOBAB

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue