Palindrome
Zeichenketten, die man sowohl von links nach rechts als auch von rechts nach links lesen kann und dabei unverändert bleiben, nennt man Palindrome (z. B. radar, madam oder racecar).
Gegeben ist eine Zeichenkette
s. Man soll bestimmen, auf wie viele verschiedene Arten man aus s ein Palindrom erhalten kann, indem man Zeichen entfernt. Es ist auch möglich, keine Zeichen zu entfernen, wenn s bereits ein Palindrom ist. Die Reihenfolge, in der Zeichen entfernt werden, spielt dabei keine Rolle.Eingabe
Die Eingabe enthält den String
s (1 ≤ |s| ≤ 60), der aus Großbuchstaben des lateinischen Alphabets besteht.Ausgabe
Das Programm soll die Anzahl verschiedener Möglichkeiten ausgeben, wie man aus
s ein Palindrom erhalten kann.Beispiele
Eingabe | Ausgabe |
BAOBAB | 22 |
Erklärung
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
BAOBAB
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB