Recherche du plus long palindrome dans une chaîne

PHP Medium strings

Tâche «Recherche du plus long palindrome dans une chaîne»

Écrivez une fonction qui prend une chaîne et trouve la sous-chaîne palindrome la plus longue. S'il y en a plusieurs, retournez la première dans l'ordre. La chaîne est composée uniquement de lettres latines minuscules. La longueur de la chaîne est de 1 à 1000 caractères. Implémentez un algorithme avec une complexité temporelle O(n²) ou mieux.

Format d\ entrée

Une seule chaîne contenant une séquence quelconque de lettres latines minuscules.

Format de sortie

Une seule chaîne — la sous-chaîne palindrome la plus longue. S'il n'y a pas de palindrome, affichez une chaîne vide.

Exemples

Exemple 1

ENTRÉE

babad

SORTIE

bab

Exemple 2

ENTRÉE

abbae

SORTIE

abba

Exemple 3

ENTRÉE

a

SORTIE

a

main.php