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
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. BAOBAB
  1. 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