Plus long palindrome

Un palindrome est un mot symétrique, c'est-à-dire un mot qui se lit de la même manière de gauche à droite que de droite à gauche. Par exemple, les mots « radar », « ressasser », « y », « ici », et « ppoopp » sont tous des palindromes. En revanche, des mots comme « dodo », ou « pouf » ne sont pas des palindromes.

Étant donné une longue séquence de lettres, votre objectif est de trouver la longueur du plus long palindrome que l'on peut trouver dans cette séquence. Par exemple, le mot « mollakayakokomassa » contient comme plus grand palindrome le mot « kayak », qui est de longueur 5.

Limites de temps et de mémoire (Python)

  • Temps : 2,5 s sur une machine à 1 GHz.
  • Mémoire : 1 000 ko.

Contraintes

  • 1 <= L <= 2 000, où L est la longueur de la séquence de lettres donnée.

Dans 50 % des tests, on a L <= 20.

Entrée

L'entrée est une unique ligne qui contient une séquence de lettres sans espaces. Tous les caractères sont des lettres minuscules non accentuées comprises entre A et Z inclus.

Sortie

Vous devez afficher un entier sur une ligne : la longueur du plus long palindrome contenu dans la séquence donnée en entrée.

Exemple

entrée :

mollakayakokomassa

sortie :

5

Source : http://www.france-ioi.org/ Créé par : Arthur Charguéraud.